Algo de répartition

Le problème exposé dans ce sujet a été résolu.

Bonjour, j’aurais besoin d’un coup de main pour construire un algo. J’imagine que c’est tout bête, mais je n’arrive pas à trouvé une méthode pour résoudre ce problème.

J’explique mon besoin, en point d’entrée j’ai :

  • une liste de données :(peut varié de 1 à N)
  • un nombre de liste dans lesquels je doit répartir les données précédente ( peut varié de 1 à 6)

J’aimerais tester toute les possibilités, par exemple pour les données [A, B, C, D] sur 2 listes :

liste 1 liste 2
[ABCD] []
[ABC] [D]
[ABD] [C]
[ACD] [B]
[AB] [CD]
[AC] [BD]
[AD] [BC]
[A] [BCD]

l’ordre dans données dans la liste et l’ordre des listes n’a pas d’importance

  • [ABC] est identique à [ACB]
  • [ABC][D] et identique à [D][ABC]

je voudrais réalisé ça en python (3.8), donc si vous avez des pistes, ou un packages qui fait ça comme par magie, je prend, merci d’avance.

+0 -0

Ton problème revient à associer un nombre (de 1 au nombre de liste) à chaque élément de la liste de donnée.

[ABCD],[]1111[ABCD], [] \equiv 1111 et [], [ABCD]2222[ABCD] \equiv 2222

Et tu pourrais ainsi utiliser itertools.product.

Par-contre, j’ai l’impression de ne pas comprendre ton problème car pour moi ton tableau n’est pas complet et il manque tous les cas où A est réparti dans la deuxième liste.

+0 -0

Je pense que ce sera plus simple d’écrire la fonction soi-même. Tu prends le premier élément, tu mets tout le reste dans la seconde liste. Pour construire ton 2e niveau, tu prends ton niveau précédent, tu rajoutes toutes les lettres (à chaque fois une) dans l’ordre et retires de la deuxième liste. Et ainsi de suite. Ton critère d’arrêt est le fait que 'D' soit le dernier élément (tu arrêtes la récursion).

+0 -0

Dans la mesure où l’ordre dans les listes n’a pas d’importance, il serait plus judicieux de poser le problème en terme d’ensembles.
Chercher sur le web "python sous ensembles"

from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    # note we return an iterator rather than a list
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

source : https://askcodez.com/comment-puis-je-trouver-tous-les-sous-ensembles-dun-ensemble-avec-exactement-n-elements.html

+0 -0

Quand on pompe une solution de la doc Python, ça peut être pas mal de citer sa source :-° Voir l’exemple powerset (et les autres exemples peuvent probablement t’être utiles).

Je pense que ce sera plus simple d’écrire la fonction soi-même

En l’occurrence c’est souvent une mauvaise idée en Python où d’une part les préfacteurs associées à la VM rendent les implémentations manuelles lentes, et d’autre part la bibliothèque standard offre plein d’abstractions pour ce genre de manipulations.

Youhou, c’est du rapide. (oui, c’est ma première sur un forum) merci à tous pour ces réponses.

Par-contre, j’ai l’impression de ne pas comprendre ton problème car pour moi ton tableau n’est pas complet et il manque tous les cas où A est réparti dans la deuxième liste.

ache

Effectivement, j’ai pas tout mis :-)

Dans la mesure où l’ordre dans les listes n’a pas d’importance, il serait plus judicieux de poser le problème en terme d’ensembles.
Chercher sur le web "python sous ensembles"

from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    # note we return an iterator rather than a list
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

source : https://askcodez.com/comment-puis-je-trouver-tous-les-sous-ensembles-dun-ensemble-avec-exactement-n-elements.html

etherpin

En surfant sur le net j’était tomber sur "more-itertools" et "itertools", mais j’avais pas plus insisté, mais avec vos explication je vais y regarder de plus prêt. merci.

Je reviens vers vous très vite

Bon ok, (j’avais oublier à qu’elle point j’aime les fonctions récursive)

from itertools import chain, combinations

def powerset(iterable : list):
    xs = list(iterable)
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))
    
def repartition(nb, data, tab, level = 0) :   
    tmp = list(powerset(data))
    tmp = list(map(lambda x : list(x), tmp))
    
    for i in tmp :
        tab[level] = i
        rst = [elem for elem in data if not elem in i]        #reste

        if not ((level + 1) == (nb-1)): 
            repartition(nb, rst, tab, level + 1)
        
        else : 
            tab[level+1] = rst
            print(tab)

# input
d    = ["A", "B", "C", "D"]
size = 2
repartition(size, d, [[]]*size)

ce qui donne :

liste 1 liste 2
[] ['A’, 'B’, 'C’, 'D']
['A'] ['B’, 'C’, 'D']
['B'] ['A’, 'C’, 'D']
['C'] ['A’, 'B’, 'D']
['D'] ['A’, 'B’, 'C']
['A’, 'B'] ['C’, 'D']
['A’, 'C'] ['B’, 'D']
['A’, 'D'] ['B’, 'C']
['B’, 'C'] ['A’, 'D']
['B’, 'D'] ['A’, 'C']
['C’, 'D'] ['A’, 'B']
['A’, 'B’, 'C'] ['D']
['A’, 'B’, 'D'] ['C']
['A’, 'C’, 'D'] ['B']
['B’, 'C’, 'D'] ['A']
['A’, 'B’, 'C’, 'D'] []

bon par contre j’arrive pas à simplifier comme je veux. J’aurais voulue ne pas générer les doublons, mais ça attendra demain. merci à tout le monde.

Euh, je sais pas je trouvais ma solution pas trop mal.

from itertools import product

d = "ABCD"
n = 2

for perm in product(range(n), repeat=len(d)):
    lists = [set() for _ in range(n)]

    for elem, listNum in zip(d, perm):
        lists[listNum].add(elem)

    for l in lists:
        print(list(l), end=' ')
    print("")

Au cas où je m’étais pas bien fait comprendre. À chaque élément de la liste des données j’associe le numéro de la liste dans laquelle il doit être présent.

+0 -0

Bon ok, (j’avais oublier à qu’elle point j’aime les fonctions récursive)

… bon par contre j’arrive pas à simplifier comme je veux. J’aurais voulue ne pas générer les doublons, mais ça attendra demain. merci à tout le monde.

JAZZ

Il suffit de couper ta liste en deux, et tu n’auras plus de doublons !!

+0 -0

Bon ok, (j’avais oublier à qu’elle point j’aime les fonctions récursive)

… bon par contre j’arrive pas à simplifier comme je veux. J’aurais voulue ne pas générer les doublons, mais ça attendra demain. merci à tout le monde.

JAZZ

Il suffit de couper ta liste en deux, et tu n’auras plus de doublons !!

etherpin

Non j’ai essayé ça marche pour 2 listes mais après ça déconne. Je regarde ça demain, je vous tiens au jus

Je testerai la solution de ache aussi

+0 -0

bon par contre j’arrive pas à simplifier comme je veux. J’aurais voulue ne pas générer les doublons, mais ça attendra demain. merci à tout le monde.

Tu peux définir un ordre sur les listes finales et ne garder que les listes triées.
Par exemple:

['A'], ['B’, 'C’, 'D']

Est triée car le plus petit élément de la première liste est plus petit (ou égale) que le plus petit élément de la seconde liste.
Pour le cas de [], on considère une valeur infinie négative ou positive.

Il y a certainement plus simple mais ça ne me vient pas là immédiatement.

+0 -0

Bon ok, (j’avais oublier à qu’elle point j’aime les fonctions récursive)

… bon par contre j’arrive pas à simplifier comme je veux. J’aurais voulue ne pas générer les doublons, mais ça attendra demain. merci à tout le monde.

JAZZ

Il suffit de couper ta liste en deux, et tu n’auras plus de doublons !!

etherpin

Non j’ai essayé ça marche pour 2 listes mais après ça déconne. Je regarde ça demain, je vous tiens au jus

Je testerai la solution de ache aussi

JAZZ Autant pour moi ça fonctionne.

Ache j’ai regarder ta solution, elle est super élégante, mais je vais rester sur ma premier version qui fonctionne. merci à tous.

Si tu as résolu ton problème, tant mieux.

Je poste quand même une solution pour faire ce que tu veux.
Je me permet car le sujet est résolu et que j’ai envie de garder le code quelque part.

from itertools import product

def order(A, B):
    if len(A) == 0:
        return len(B) == 0
    elif len(B) == 0:
        return True

    return min(A) < min(B)

def isSorted(l):
    return all(order(A, B) for A, B in zip(l, l[1:]))



d = "ABCD"
n = 2

for perm in product(range(n), repeat=len(d)):
    lists = [set() for _ in range(n)]

    for elem, listNum in zip(d, perm):
        lists[listNum].add(elem)

    if isSorted(lists):
        for l in lists:
            print(list(l), end=' ')
        print("")
+0 -0

@fred1599: Oui merci ! Je me suis pris là tête un peu trop.

Après je pense qu’on peut faire mieux de manière générale au niveau de l’algo pour n’avoir que le résultat qu’on souhaite. De manière à ce que ça scale.

+0 -0

Salut,

C’est un problème intéressant. Comme @ache et les autres, je n’ai pas trouvé d’algorithme standard qui donnerait la solution sans devoir filtrer ou retravailler la sortie. Du coup j’ai essayé de résoudre à la main, et au final c’est pas si compliqué:

from copy import deepcopy

def generate(symbols, nb_empty_lists, current=[]):
    # end of recursion
    if len(symbols) == 0:
        return [ current + [[] for _ in range(nb_empty_lists)] ]

    head, *tail = symbols
    res = []

    # 1st possibility: add the head symbol to an existing list
    for i in range(len(current)):
        cpy = deepcopy(current)
        cpy[i].append(head)
        res.extend(generate(tail, nb_empty_lists, cpy))

    # 2nd possibility: create a new list for the head symbol
    if nb_empty_lists > 0:
        res.extend(generate(tail, nb_empty_lists - 1, current + [[head]]))

    return res

# Example
for sol in generate("ABCD", 3):
    print(', '.join(map(str, sol)))
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte