Suite de Skolem

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une suite de Skolem d’ordre n est une suite de 2n entiers, constituée des entiers de 1 à n répétés chacun deux fois, les deux occurrences d'un entier k étant distantes de k. Une suite de Langford en est la variante où les occurrences de k sont distantes de k+1.

Plus formellement, une suite de Skolem est de la forme (S1, … , S2n ), avec :

  • pour chaque k dans l’ensemble {1,2,3, … , n}, il y a exactement deux indices i et j pour lesquels Si = Sj = k ;
  • si Si = Sj = k avec i < j alors j - i = k.

La suite des Si - 1 possède alors la même propriété qu'une suite de Langford (les deux occurrences de k y sont distantes de k + 1), mais cette suite prend ses valeurs de 0 à n - 1 (tandis qu'une suite de Langford prend ses valeurs de 1 à n ).

Par exemple, 4,2,3,2,4,3,1,1 est une suite de Skolem d’ordre 4.

Il n’existe de suite(s) de Skolem d’ordre n que si n est congru à 0 ou 1 modulo 4[1]. (Cette restriction tombe dans le cas des "suites de Skolem étendues", comprenant en plus l'entier 0.)[réf. souhaitée]

La restriction analogue pour les suites de Langford[2] est : n congru à 0 ou 3 modulo 4.

On ne connait pas de formule générale donnant, dans ces cas, le nombre de suites de Skolem ou de Langford d'ordre n, mais seulement des algorithmes pour les énumérer.

Les suites de Skolem ont été décrites par le mathématicien norvégien Thoralf Skolem.

Exemple de programme en Python[modifier | modifier le code]

#!/usr/bin/python
#-*- encoding: utf8 -*-
"""
skolem_class.py

Une suite de Skolem d'ordre n est une suite (a1, a2.....a2n) dont les 2n valeurs 
sont les entiers de 1 à n, pris chacun 2 fois, et rangés dans un ordre tel que la 
différence des rangs de 2 occurrences d'un entier p soit justement p.

Il n'existe pas de suite de Skolem ordre 2 et 3, ni de tout ordre dont le reste 
de la division par 4 est 2 ou 3.
nb solutions pour n =
    1       :   1
    2, 3    :   0
    4       :   6
    5       :   10
    6, 7    :   0
    8       :   504
    9       :   2656
    10, 11  :   0    
    12      :   455936
    13      :   3040560
remarque
4xxx4
42x24
42324311

8xxxxxxx8
86xxxxx68
864xxx468
864x7x468xx7
864272468xx7
8642724683x7311
8642724683573115

Une paire de chiffres identiques peut être considérée comme une pièce qu'il faut placer 
à côté des autres dans un univers de 2 * n positions (sans débordement).

Algorithme :
    Variables :
n : ordre de la suite Skolem
s : nombre de solutions 

p(1 à n) : codage position des paires d'entier (0 = non placé/non valide)
k :indice de boucle de la pièce placée
j : indice de boucle.

Il y a plusieurs pièces 
11     2.2    3..3    4...4    5....5    6.....6

Si p[i] est la position d'un entier, la position du second est obtenue en p[i] + i

Pour en un minium de tests, il faut éviter de mettre deux chiffres (ou nombre) dans la même position.
Pour vérifier que la pièce n° k n'interfère avec aucune des autres pièces, il faut tester 
les égalité suivantes : p[k] = p[j], p[k] = j + p[j], k + p[k] = p[j], k + p[k] = j + p[j]
Il faut aussi veiller à ce que i + p[i] <= 2*n
On commence par placer la pièce la plus grande (pièce n) à la première position et 
on cherche ensuite à placer les pièces de taille inférieure dans les positions libres restantes. 
Si on arrive à placer toutes les pièces (c'est-à-dire à placer le doublé 11), alors c'est qu'on
a trouvé une solution. On l'affiche et on poursuit la recherche d'une autre solution.
Lorsqu'une pièce ne peut être placée, alors l'algorithme rebrousse chemin : on considère que la 
branche de recherche sur laquelle il se trouve est terminée. On revient alors la position de la 
pièce précédente dont on cherche la position possible suivante. Avant de repartir à zéro.
S'il advient qu'on ne trouve plus de positions pour la plus grande pièce, alors c'est qu'on a fait le tour des possibilités. 

Petit exemple avec n=4

k | p[k] | Suite 
--+------+---------------  
4 |    1 | [4...4...]      Ok passons au suivant :
3 |    1 |                Impossible P(3)=P(4)  (interférence premier 4 et premier 3)
3 |    2 |                Impossible 3+P(3)=P(4) (interférence second 3 avec premier 4)
3 |    3 | [4.3.43..]
2 |    1 |                Impossible P(2)=P(4)
2 |    2 | [423243..]     Ok passons au suivant
1 |    1 |                Impossible P(1)=P(4)
1 |    2 |                Impossible P(1)=P(2)
1 |    3 |                Impossible P(1)=P(3)
1 |    4 |                Impossible P(1)=2+P(2) (interférence avec le second 2)
1 |    5 |                Impossible P(1)=4+P(4) (interférence avec le second 4)
1 |    6 |                Impossible P(1)=3+P(3) (interférence avec le second 3)
1 |    7 | [4234311]      Ok première solution trouvée.
"""


class skolem_class():
    #------------------------
    def getSolutions(self):
        return self.solutions
    #------------------------
    def retourAr(self):
        self.p[self.k] = 0
        self.k = self.k + 1
        if self.k > self.n :
            self.finOk = True
        else : 
            self.bcl1 = True
            self.bcl2 = False
    #-------------------------       
    def __init__(self, ordre):
        self.n = ordre
        self.k = ordre
        self.p = []
        self.solutions = []
        a = []
        j = 0

        for i in range(2 * self.n ):
            a.append(0)
        for i in range(self.n + 1):
            self.p.append(0)
        
        self.finOk = False
        self.bcl2 = False
        self.bcl1 = True
        
        while self.k <= self.n or self.finOk == False :
            if self.bcl1 == True and self.bcl2 == False:
                self.bcl2 = True
                self.bcl1 = False
                j = self.k
                self.p[self.k] = self.p[self.k] + 1
                if self.k + self.p[self.k] > 2 * self.n:
                    self.retourAr()
            
            if self.finOk == False and self.bcl2 == True and self.bcl1 == False:
                j = j + 1
                if j <= self.n:
                    if self.p[self.k] == self.p[j] or self.p[self.k] == j + self.p[j]  or self.k + self.p[self.k] == self.p[j] or self.k + self.p[self.k] == j + self.p[j]:
                        self.bcl2 = False
                        self.bcl1 = True
                    else: 
                        self.bcl2 = True
                        self.bcl1 = False
                else:
                    # on place la pièce dans 2 positions
                    a[self.p[self.k] -1]         = self.k # -1 pour début à index 0
                    a[self.k + self.p[self.k]-1] = self.k
                    # construction de la solution intermédiaire 
                    # print self.k, '> ', a
                    
                    self.k = self.k - 1
                    if self.k > 0:
                        self.bcl1 = True
                        self.bcl2 = False
                    else:
                        # solution trouvée = a
                        self.k = 1
                        # print 'solution : ', a
                        
                        # création liste b différente de a pour ajout dans liste solutions
                        b = []  
                        for x in range(len(a)):
                            b.append(a[x])
                        self.solutions.append(b)
                                          
                        self.retourAr()
        # while self.k <= self.n of self.finOk == False   
        #--------------------------
if __name__ == "__main__":
    ordre = 8
    print 'Suite de skolem, ordre :', ordre
    print 'Traitement en cours...........'
    listeSol = skolem_class(ordre).getSolutions()

    for i in range(len(listeSol)):
        print ' sol : ', i+1, ' > ', listeSol[i]
    str = raw_input("Valider pour finir");
#------------------------------------------------        
"""
n=4   6.solutions    { 42324311   41134232   34232411   11423243   23243114   11342324 }
n=5  10.solutions    { 5242354311 5113453242 4511435232 3523245114 3453242511 1152423543 4115423253 2325341154 2423543115 1134532425 }
n=8 504.solutions    { 8572625487643113  8473643587625211   8374356487526211  8272356387546114   8372326487546115  8272115687453643   
                       8627245684753113  8647114685723253   8637232685741154  8357346584726211   8427245683753611  8457242586731136
                       8642724683573115  8252746584376311   8411746385376252  8242754683573611   8112724685473653  8411743683572625
                       8113743684572625  8534735486272116   8453743586272116  8232734586475116   8611574685437232  8611272685347354
                       8611272684537435  8526275486347311   8526275386347114  8356374586427211   8116375386457242  8252673583647114
                       8113673485647252  8511375386427246   8631137685242754  8116357386542724   8112627485643753  8451147586232736
                       8352327586411746  8311357486542724   8346354786511272  8511645784623273   8411645783653272  8112526785346373
                       8311346784526272  7825264758463113   7811262758463543  7823263748564115   7811456748536232  7841154768523263
                       7823253768541164  6857116548734232   6837436548725211  6827236538745114   5867252468743113  4867425268753113
                       4867411568735232  4857462528763113   4857436538726211  5847354368711262   4857411568723263  6852726548374311
                       6811736538475242  6834736458272511   6811726258473543  3863711568475242   2824736438576115  5811752628473643
                       2825711658473643  2823753648574611   3843724268571165  6851176538437252   6825276458347311  6825276358347114
                       6824276438537115  3863272468547114   3853672528647114  2823673458647511   4811472628537635  4853473568117262
                       4811475368357262  5861157368342724   3863117468542724  3853467548262711   5824257468113763  5811357368242764
                       4852427568113763  3853117568242764   2821157468543763  4811456748523273   6831136758242574  6831136748524275
                       5861154768423272  4863453768511272   3863252768541174  2821164758463573   2823463748561175  4835436758116272
                       2825116758346374  4811456738536272   4811436738526275  6824256478531137   6831136578425247  4853463578262117
                       3853262578461147  3823264578465117   5811356378426247  3853116578426247   3823256478546117  5841154678232637
                       5823253678411647  7586115746834232   7386311756842524  7385346754826211   7282536735846114  ...
"""

Notes et références[modifier | modifier le code]