Partage

[Exercice] Règle de Golomb

21 juillet 2011 à 14:12:05

Bonjour,

Voici un exo pour s'entrainer avec Python.

Présentation

En mathématiques, une règle de Golomb est une règle, munie de marques à des positions entières, telle que deux paires de marques ne soient jamais à la même distance ; en d'autres termes, chaque couple de marques mesure une longueur différente des autres.

Exemple de règle (source: Wikipédia) :
Image utilisateur

Quelques définitions :

l'ordre d'une règle de Golomb signifie le nombre de marques présentes. La règle ci-dessus est d'ordre 4.
la longueur d'une règle de Golomb représente l’écart maximal entre 2 de ses marques. (par convention, la règle commence à zéro, donc c'est la valeur de la plus haute marque). La longueur de la règle ci-dessus vaut 6.
une règle de Golomb est dite optimale si sa longueur est la longueur minimale pour son ordre. La règle ci-dessus est optimale.
une règle de Golomb est dite parfaite si elle permet de mesurer toutes les longueurs entre 1 et n (n = longueur). La règle ci-dessus est aussi parfaite.

La recherche s’intéresse beaucoup à ces règles, notamment du fait qu'il est très difficile de vérifier qu'une règle un peu grande est optimale. C'est l'un des objets du projet de calcul distribué distributed.net (page du projet). Pour vous faire une idée, le dernier résultat en date est la longueur d'une règle d'ordre 26... Mais rassurez vous, nous ne ferons que des choses abordables en terme de temps de calcul.

Pour avoir plus d'informations, ou si vous ne comprenez pas quelque chose, vous pouvez consulter la page Wikipédia.

Ce que vous devez faire :

Exercice 1 (niveau facile) :

Coder une fonction qui prends une règle candidate en entrée (même format que sur l'image), et retourne un tuple de booléens (Valide, Parfaite).

Exercice 2 (niveau moyen) :

Réaliser une fonction prenant en paramètre un ordre et une longueur, et retournant toutes les règles de Golomb trouvées pour ces paramètres.

GurneyH

21 juillet 2011 à 17:22:55

Une solution pour le premier exercice pour commencer.

# -*- coding: utf-8 -*-

def test(marques):
    if min(marques) != 0:
        return (False, False)
    
    ecarts = [0] * (max(marques) + 1)
    ecarts[0] = 1
    for (i, m1) in enumerate(marques):
        for m2 in marques[:i]:
            ecarts[abs(m1 - m2)] += 1

    valide, parfaite = True, True
    for d in ecarts:
        if d == 0:
            # l'écart n'est pas mesuré
            parfaite = False
        elif d != 1:
            # l'ecart est mesuré plusieurs fois
            valide = False

    return (parfaite, valide)
    

print test([0, 1, 4, 6])

edit:
renommé au dernier moment, et paf. :-°

Zeste de Savoir, le site qui en a dans le citron !

yoch

21 juillet 2011 à 17:34:51

Salut,

Une petite typo :

return (perfect, valid)

C'est plutôt :

return (valide, parfaite)

Plus embêtant, ton code (modifié) retourne (False, True) pour cette entrée : [0, 1, 2, 3, 4, 5], alors que c'est (False, False) (on peut difficilement avoir une règle invalide et parfaite

).

Sinon passe mes autres tests.

GurneyH

21 juillet 2011 à 17:39:14

En effet.

J'ai corrigé ainsi

elif d != 1:
    # l'ecart est mesuré plusieurs fois
    valide, parfaite = False, False

edit:
Et le second.
On est d'accord, on doit afficher TOUTES les règles de Golomb, pas seulement les règles optimales?

# -*- coding: utf-8 -*-

def test(marques):
    if min(marques) != 0:
        return (False, False)
    
    ecarts = [0] * (max(marques) + 1)
    ecarts[0] = 1
    for (i, m1) in enumerate(marques):
        for m2 in marques[:i]:
            ecarts[abs(m1 - m2)] += 1

    valide, parfaite = True, True
    for d in ecarts:
        if d == 0:
            # l'écart n'est pas mesuré
            parfaite = False
        elif d != 1:
            # l'ecart est mesuré plusieurs fois
            valide, parfaite = False, False

    return (valide, parfaite)
    

def golomb(ordre, longueur):
    solutions = []
    crt = [0]
    def mk_golomb(marque):
        if len(crt) == ordre:
            solutions.append(crt[:])
        else:
            for i in range(marque, longueur + 1):
                crt.append(i)
                valide, parfaite = test(crt)
                if valide:
                    mk_golomb(i + 1)
                crt.pop()
    mk_golomb(1)
    return solutions



for s in golomb(5, 11):
    print s

Zeste de Savoir, le site qui en a dans le citron !

yoch

22 juillet 2011 à 11:46:46

Citation : GurneyH

edit:
Et le second. [...]

Félicitation !

Ton code est bon, et assez performant, je trouve. Tu n'est pas tombé dans le piège de la version naïve.

Version naïve:

from itertools import combinations

def golomb_naif(order, length):
    ret = []
    for ruler in combinations(list(range(length+1)), order):
    valid,_ =  test(ruler)      
    if valid:
        ret.append(ruler)
    return ret

Citation : GurneyH

On est d'accord, on doit afficher TOUTES les règles de Golomb, pas seulement les règles optimales?

Oui, on est bien d'accord, c'est logique puisque on définit une longueur pour notre règle : cette longueur peut-être possible ou non, optimale ou non...

_______

Ma version de l'exercice 2 (que je posterai plus tard) a une approche totalement différente : je considère la règle d'un point de vue d’écarts plutôt que de marques. Cela donne un code totalement différent.

Sinon, pour l'exo 1, j'ai aussi codé d'une manière assez différente de la tienne (je trouve ta façon assez C, c'est d'ailleurs intéressant pour moi de voir comment tu t'y prends

), mais des benchs donnent ton code plus performant. On peut simplifier ton code si on considère que la règle en entrée suit un format précis (commence à 0, et les marques sont ordonnées) :

def test(marques):
    ecarts = [1] + [0] * marques[-1]
    for i, m1 in enumerate(marques):
        for m2 in marques[:i]:
            ecarts[m2 - m1] += 1
    for d in ecarts:
        if d > 1:
            # l'ecart est mesuré plusieurs fois
            return False, False
    return True, all(ecarts)

Merci pour ta participation !

PS: n'y a il personne pour nous pondre un code pour les règles d'ordre > 10 ? Je n'ai pas réussi pour l'instant. :-°

nohar

23 juillet 2011 à 0:55:54

Plop.

Voilà ma contribution pour l'exo 1:

#!/usr/bin/env python2
# -*- coding: utf-8 -*-

def evaluate(rule):
    lengths = []
    for idx, mark in enumerate(rule):
        lengths += [mark - other for other in rule[:idx]]

    valid = not reduce(lambda acc, val: lengths.count(val) > 1 or acc, 
                       lengths, False)

    perfect = len(lengths) == max(lengths)
    
    return (valid, valid and perfect)

Et un petit programme de test :

if __name__ == '__main__':
    tests = [[0, 1, 2, 3, 4, 5], [0, 1, 5, 11], [0, 1, 4, 6]]
    print "Exo 1: "
    for t in tests:
        print t, '->', evaluate(t)

Exo 1:
[0, 1, 2, 3, 4, 5] -> (False, False)
[0, 1, 5, 11] -> (True, False)
[0, 1, 4, 6] -> (True, True)

Je cherche encore une solution élégante pour le second.

Zeste de Savoir, le site qui en a dans le citron !

GurneyH

23 juillet 2011 à 1:10:49

Au moins, tu as une version élégante pour le premier!

et, c'est ta version qu'on attendait en fait

Zeste de Savoir, le site qui en a dans le citron !

nohar

23 juillet 2011 à 17:02:04

Voilà pour l'exo 2:

def golomb_rulers(order, length, used=set(), offset=0):
    add_offset = lambda elt: offset + elt
    if order == 2:
        if length not in used:
            yield [offset, offset + length]
        return
    
    for cur_len in set(xrange(1,length)) - used:
        if any((length - cur_len in used, length - cur_len == cur_len, 
                length - offset == 2 * cur_len)): continue

        for ruler in golomb_rulers(order - 1, length - cur_len, 
                                used | set([cur_len, cur_len+offset, length]),
                                cur_len):
            lengths, candidate = [], [0] + ruler
            for idx, mark in enumerate(candidate):
                lengths += [mark - other for other in candidate[:idx]]
            
            if any(lengths.count(l) > 1 for l in lengths): continue
            yield list(map(add_offset, candidate))

C'est pas très élégant (le code sent un peu la sueur) parce que je suis encore obligé de tester la validité explicitement, mais j'ai la flemme de chercher plus loin.

Quoi qu'il en soit, ce code est capable (même si c'est très long) de trouver des règles de Golomb d'ordre > 10.

Voilà un petit programme de test :

if __name__ == '__main__':
    print "\nExo 2: ",
    to_test = [(2,1), (3,3), (4,6), (5,11), (6,17), (7,25), (8,34), (9, 44), (10,55)]
    for ordre, longueur in to_test:
        print "\nordre {}, longueur {}".format(ordre, longueur)
        for r in golomb_rulers(ordre, longueur):
            print r, '->', evaluate(r)

Zeste de Savoir, le site qui en a dans le citron !

yoch

23 juillet 2011 à 21:11:13

@nohar :
Merci pour ta participation. Je vais me pencher attentivement sur tes codes.

Simple question : est ce que le fait de changer le xrange() de ton second code par range (python 3.2 oblige) a une quelconque incidence sur les perfs ? J'ai mesuré les performances pour l'ordre 9 entre ta fonction (remplacé xrange par range) et la mienne, et la tienne est meilleure, mais je n'ose pas tenter pour un ordre > 10 :-°

yoch :
[[0, 1, 5, 12, 25, 27, 35, 41, 44], [0, 3, 9, 17, 19, 32, 39, 43, 44]]
[11.138000s]

nohar :
[[0, 1, 5, 12, 25, 27, 35, 41, 44], [0, 3, 9, 17, 19, 32, 39, 43, 44]]
[8.408000s]

________

Bon, je poste mes codes (l'explication de mon approche se trouve ci-dessus) :

Exercice 1 :

def isPerfect(l):
    return sorted(l) == list(range(1, len(l) + 1))

def isValid(ruler):
    l = []
    for i in range(len(ruler)):
        for j in range(i+1, len(ruler)):
            l += [ruler[j]-ruler[i]]
    return (len(l) == len(set(l)), isPerfect(l))

soit un peu plus court :

def isValid2(ruler):
    l = []
    for i in range(len(ruler)):
        l += list(map(lambda x: x-ruler[i], ruler[i+1:]))
    return (len(l) == len(set(l)), isPerfect(l))

Exercice 2 :

from functools import reduce

def gen_ruler(order, length):
    ecart_max = length - reduce(lambda acc,x: acc + x, [n for n in range(order-1)])
    _candidates = {n + 1 for n in range(ecart_max)}
    ret = []
    # fonction récursive : recoit les écarts candidats, ainsi que les marques et les écarts de la règle
    # certaines variables sont locales à la fonction parente
    def gen_rec(candidates, marques, ecarts):
        if len(marques)==order and marques[-1]==length:
            ret.append(marques)
        elif len(marques)<order and marques[-1]<length:
            for n in candidates:
                m = n + marques[-1]
                e = {m - m2 for m2 in marques}      # e = set(map(lambda x: m - x, marques))
                if ecarts.isdisjoint(e):
                    gen_rec(candidates - {n}, marques + [m], ecarts | e)
    # fin fonction gen_rec()
    gen_rec(_candidates, [0], set())
    return ret

EDIT : pour l'ordre 10 (len : 55)

yoch :
[[0, 1, 6, 10, 23, 26, 34, 41, 53, 55], [0, 2, 14, 21, 29, 32, 45, 49, 54, 55]]
[111.930000s]

nohar :
[[0, 1, 6, 10, 23, 26, 34, 41, 53, 55], [0, 2, 14, 21, 29, 32, 45, 49, 54, 55]]
[110.058000s]

PS: Au passage, on peut remarquer qu'à moins d’être symétrique, toute règle forme une règle inversée différente de même longueur (c'est d'ailleurs le cas pour les règles ci-dessus). Je ne sais pas si ça peut permettre d'optimiser...

EDIT 2 : Après analyse approfondie, je pense que la grande faiblesse de mon code est qu'il est très difficile de prédire correctement l’écart maximum entre deux marques (les prédictions sont nettement au dessus de la réalité), et que sans cela tout le gain potentiel d'efficacité est réduit à néant...

Je propose donc un nouveau code (approche classique cette fois) :

def _gen_ruler2(order, length):
    if order == 1:
        yield [0], set()
    else:
        for ruler,used in _gen_ruler2(order - 1, length):
            for mark in range(ruler[-1] + 1, length + 1):
                t = {mark - m for m in ruler}
                if mark <= length and used.isdisjoint(t):
                    yield ruler + [mark], used | t

def gen_ruler2(order, length):
    return [r for r,_ in _gen_ruler2(order, length) if r[-1]==length]

yoch:
[[0, 1, 6, 10, 23, 26, 34, 41, 53, 55], [0, 2, 14, 21, 29, 32, 45, 49, 54, 55]]
[77.254000s]

nohar:
[[0, 1, 6, 10, 23, 26, 34, 41, 53, 55], [0, 2, 14, 21, 29, 32, 45, 49, 54, 55]]
[107.749000s]

colbseton

25 juillet 2011 à 12:51:20

Salut,

Je me permets de poster une version en Haskell (pour l'exercice 1) car je trouve que ces exos ont aussi bien leur place sur ce forum, que sur AL.

L'idée quand j'ai créé ce code, c'était de jouer avec des tuples. On forme tous les couples possibles d'une listes. Ensuite, vu que mon algo est mauvais, on supprime les doublons en triant d'abord la liste avec les couples (les fonctions couple, couple' et uniq se chargent de ça).

couple (x:xs) = couple' x xs

couple' :: Int -> [Int] -> [(Int, Int)]
couple' x [] = [(x, x)] -- je considère qu'une règle à élément ce découpe comme cela
couple' x [y] = [(x, y)]
couple' x (y:ys) = 
  (x, y) : (couple $ x:ys) ++ (couple $ y:ys)

uniq [] = []
uniq (x:xs) = x : uniq (dropWhile (\y -> y == x) xs)

-- dropWhile retourne les suffixes restants dans la liste 
-- (ceux qui renvoient vrais sur la fonction que l'on passe en paramètre
-- par exemple : dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]

f = uniq . sort . couple -- une fonction qui compose les autres

La fonction principale est isGolomb, la voici commentée :

isGolomb [] = (False, False) -- une liste vide renvoie (False, False)
isGolomb list@(x:xs) = -- le list@ n'est qu'un alias du pattern, ça permet de s'en resservir ensuite
  let cpl = f list in -- on forme les couples de la listes
  let diff = map (\(x,y) -> abs (x-y)) cpl in -- on calcule leur différence

    -- si la liste obtenue (avec les différences) est 
    -- la même que celle à qui on "essaie" d'enlever les doublons, c'est que toutes les longueurs sont différentes
    if sort diff == (uniq $ sort $ diff) then
      if isPerfect diff (maximum list) then -- on teste si la liste est parfaite ou non
        (True, True) else (True, False)
    else (False, False)

La seconde fonction, isParfaite commentée :

isPerfect [] _ = False -- une liste vide renvoie False
isPerfect list y = -- dans les autres cas…
  if maximum list == y then -- si la longueur maximale == la marque la plus haute
    if length(z) == length(list) - 1  then 
      True else False
  else False
  where z = filter (==1) $ map (\(x,y) -> abs (x-y)) $ f list
  -- ici on filtre les longueurs == 1 (on prend en fait tous les couples de la liste deux à deux via f) :
  -- [1, 2, 3, 4] -> [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)] ->[abs(1,2), abs(2,3), abs(3,4)]
  -- et on remarque qu'il existe une relation entre le nombre de ces couples et le nombre de couples de la liste initiale
  -- et si le nombre de différence - 1 == la liste filtrée, notre règle est parfaite !

J'essaie de reprendre un exemple simple.
rules = [0,1,4,6], les couples possibles sont : [(0,1), (0,4), (0,6), (1,4), (1,6), (4,6)].
En calculant leur différence on obtient (en valeur absolue) [1, 4, 6, 4, 5, 2]. On remarque qu'il n'y a pas de doublon, donc la règle est valide.
Ensuite, on passe cette liste à isPerfect. On applique f à la nouvelle liste (l'histoire se répète), ce qui nous donne quelque chose que j'ai la flemme de faire à la main

. Et via la fonction filter, on filtre toutes les longueurs non égales à 1.
On a donc [1, 1, 1, 1, 1]. Et la longueur de ce truc est égale à 1 + la longueur de la liste initiale => règle parfaite.

J'ai pas fait dans le cas général, je sais pas si je suis clair, mais en gros ça revient à jouer avec les distances et légèrement les combinaisons (et faut bien avoir en tête quels tuples on manipule et à quel moment :-°

).
D'ailleurs voici le code en entier :

import Data.List

couple (x:xs) = couple' x xs

couple' :: Int -> [Int] -> [(Int, Int)]
couple' x [] = [(x, x)]
couple' x [y] = [(x, y)]
couple' x (y:ys) = 
  (x, y) : (couple $ x:ys) ++ (couple $ y:ys)

uniq [] = []
uniq (x:xs) = x : uniq (dropWhile (\y -> y == x) xs)

f = uniq . sort . couple

isPerfect [] _ = False
isPerfect list y = 
  if maximum list == y then
    if length(z) == length(list) - 1  then 
      True else False
  else False
  where z = filter (==1) $ map (\(x,y) -> abs (x-y)) $ f list


isGolomb [] = (False, False)
isGolomb list@(x:xs) = 
  let cpl = f list in
  let diff = map (\(x,y) -> abs (x-y)) cpl in
    if sort diff == (uniq $ sort $ diff) then
      if isPerfect diff (maximum list) then 
        (True, True) else (True, False)
    else (False, False)

main = 
  print $ isGolomb [0, 1, 5, 11]

elnorreip

28 février 2012 à 13:31:02

Bonjour,

Je me permets de poster une seconde version Haskell, plus concise et peut être plus élégante de l'exercice 1.

Pour créer cette version Haskell, je suis parti de l'énoncé du problème et pas de la solution.

Enoncé 1 : Une règle de longueur l est dite valide si tous les écarts sont uniques
Ce qui peut se traduire en Haskell par :

valide r = unique $ ecarts r where
  unique [x]    = True
  unique (x:xs) = not (x `elem` xs) && unique xs

La liste des écarts définis par la règle r est construite au moyen d'une liste en compréhension :

ecarts r = [ abs((r !! i) - (r !! j)) 
           | i <- [1..(length r)-1], j <- [0..i-1]]

Enoncé 2 : Une règle de longueur l est dite parfaite, si tous les écarts de 1 à l sont mesurés une fois et une seule fois.
Autrement dit c'est une règle valide, dont la liste des écarts définis est de même longueur que la liste des écarts à calculer soit :

parfaite r = valide r && le == l where
	     l = maximum r
	     le = length (ecarts r)

Programme complet

Le programme complet avec un jeu de test :

ecarts r = [ abs((r !! i) - (r !! j)) 
           | i <- [1..(length r)-1], j <- [0..i-1]]

valide r = unique $ ecarts r where
  unique [x]    = True
  unique (x:xs) = not (x `elem` xs) && unique xs

parfaite r = valide r && le == l where
	     l = maximum r
	     le = length (ecarts r)
	   
-- Jeu de test pour le programme
tests = [[0, 1, 2, 3, 4, 5], [0, 1, 5, 11], [0, 1, 4, 6],
         [0, 1, 5, 12, 25, 27, 35, 41, 44], 
         [0, 3, 9, 17, 19, 32, 39, 43, 44],
	 [0, 1, 6, 10, 23, 26, 34, 41, 53, 55],
	 [0, 2, 14, 21, 29, 32, 45, 49, 54, 55]]

-- Programme principal
main = do
  putStrLn "Exo 1 :"
  mapM_ putStrLn (map golombCheck tests) where
	golombCheck r = show r ++ " => " ++ show (valide r, parfaite r)

Exécution du jeu de test

runhaskell golomb_rulers.hs
Exo 1 :
[0,1,2,3,4,5] => (False,False)
[0,1,5,11] => (True,False)
[0,1,4,6] => (True,True)
[0,1,5,12,25,27,35,41,44] => (True,False)
[0,3,9,17,19,32,39,43,44] => (True,False)
[0,1,6,10,23,26,34,41,53,55] => (True,False)
[0,2,14,21,29,32,45,49,54,55] => (True,False)

Génération de règles

Le programme de génération de règles est aussi simple en utilisant la fonction de la bibliothèque Data.List : subsequences.
Les règles de Golomb sont toutes les sous-séquences valides de longueur ordre de la liste des entiers de 0 à la longueur de la règle.

import Data.List  -- pour la fonction subsequences

generation ordre l =  [ rule | 
             r <- subsequences [1..l-1], 
             length r == ordre-2,
	     let rule = [0] ++  r ++ [l],
             valide rule]

Quelques exemples :

> generation 4 6
[[0,1,4,6],[0,2,5,6]]
> generation 5 11
[[0,2,7,8,11],[0,1,4,9,11],[0,3,4,9,11],[0,2,7,10,11]]
> generation 6 17
[[0,1,4,10,12,17],[0,1,8,11,13,17],[0,1,8,12,14,17],[0,1,4,10,15,17],[0,3,5,9,16,17],[0,4,6,9,16,17],[0,2,7,13,16,17],[0,5,7,13,16,17]]
> generation 7 25
[[0,2,3,10,16,21,25],[0,2,7,13,21,22,25],[0,1,4,10,18,23,25],[0,3,4,12,18,23,25],[0,1,11,16,19,23,25],[0,1,7,11,20,23,25],[0,4,9,15,22,23,25],[0,2,6,9,14,24,25],[0,2,5,14,18,24,25],[0,2,7,15,21,24,25]]

Attention cet algorithme est très lent, car il crée et valide les 2^n sous-séquences de la liste des nombres de 1 à n, n étant la longueur de la règle - 2. Pour la dernière génération ci-dessus le programme doit tester 2^23 (8 388 608) sous-séquences.

Version 2

Une version un peu améliorée de la précédente en ne sélectionnant que les n-uplets de longueur ordre au lieu de tous les n-uplets et ensuite vérification de l'ordre.

generation' ordre l =  [ rule | 
             r <- tuples (ordre - 2) [1..l-1], 
	     let rule = [0] ++  r ++ [l],
             valide rule] 

tuples 0 _      = [[]]
tuples _ []     = []
tuples n (x:xs) = (map (x:) (tuples (n-1) xs)) ++ (tuples n xs)

Version 3

Cette fois on va prendre une approche un peu différente en utilisant un générateur de règles valides.
Le générateur part d'une règle valide, dont les marques sont classées dans l'ordre décroissant et ajoute une marque en tête pour créer une nouvelle règle, si elle est valide elle sert de générateur pour d'autres règles.

genRules seed l = seed : [rule | i <- [(head seed)+1..l],
                          let r = i : seed,
		          valide r,
			  rule <-genRules r l]

Maintenant nous pouvons utiliser ce générateur de règles pour notre fonction principale à la place de subsequences et de tuples, et en modifiant légèrement le programme car les règles créées sont déjà valides.

generation'' ordre l =  [ rule | 
             rule <- genRules [0] l, 
	     length rule == ordre]

Et le programme principal pour appeler cette fonction :

rules = [(2,1),(3,3),(4,6),(5,11),(6,17),(7,25),(8,34),(9,44),(10,55),(11,72)]

main = do
  putStrLn "Exo 2 :"
  mapM_ (print . genere) rules where
	genere (o,l) = generation'' o l