Algo de répartition

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 :

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.

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).

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.

Effectivement, j’ai pas tout mis :-)

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 :

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.

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

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

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.

Comme Ache.

Garder uniquement les solutions où A est dans la 1ère colonne, ce serait une solution, mais si size devient plus grand que 2, la généralisation serait un peu complexe.

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("")

Bonjour,

@ache,

Peut-être un équivalent pour la fonction order,

def order_bis(A, B):
    if A and B:
        return min(A) < min(B)
    return not bool(B)

@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.