Comment puis-je partitionner au maximum un ensemble?

Question

J'essaie de résoudre un des problèmes de Project Euler. Par conséquent, j'ai besoin d'un algorithme qui m'aidera à trouver toutes les partitions possibles d'un ensemble, dans n'importe quel ordre.

Par exemple, compte tenu de l'ensemble 2 3 3 5:

2 | 3 3 5 
2 | 3 | 3 5 
2 | 3 3 | 5 
2 | 3 | 3 | 5 
2 5 | 3 3 

et ainsi de suite. Presque toutes les combinaisons possibles des membres de l'ensemble. J'ai bien sûr cherché sur le net, mais je n'ai pas trouvé beaucoup de choses qui me soient directement utiles, puisque je parle programmeur-ese pas avancé-math-ese.

Quelqu'un peut-il m'aider avec ça? Je peux lire à peu près n'importe quel langage de programmation, de BASIC à Haskell, alors publiez dans la langue que vous souhaitez.

Answer 1

Avez-vous considéré un arbre de recherche? Chaque nœud représenterait un choix d'où placer un élément et les nœuds de feuille sont des réponses. Je ne vous donnerai pas de code parce que cela fait partie du plaisir de Project Euler;)

Answer 2

Eh bien, le problème a deux aspects.

Tout d'abord, les articles peuvent être disposés dans n'importe quel ordre. Donc pour N objets, il y a N! permutations (en supposant que les éléments sont traités comme uniques).
Deuxièmement, vous pouvez envisager le regroupement comme un indicateur de bit entre chaque élément indiquant une division. Il y aurait N-1 de ces drapeaux, donc pour une permutation donnée il y aurait 2^(N-1) groupements possibles.
Cela signifie que pour N éléments, il y aurait un total de groupements/permutations N! * (2^(N-1)), qui devient très très rapide.

Dans votre exemple, les quatre premiers éléments sont des regroupements d'une permutation. Le dernier élément est un regroupement d'une autre permutation. Vos articles peuvent être considérés comme:

2 sur 3 sur 3 sur 5
2 sur 3 sur 3 sur 5
2 sur 3 sur 3 sur 5
2 sur 3 sur 3 sur 5
2 sur 5 on 3 off 3

Les permutations (l'ordre d'affichage) peuvent être dérivées en les regardant comme un arbre, comme mentionné par les deux autres. Cela impliquerait certainement la récursivité, comme here. Le groupement est indépendant d'eux de plusieurs façons. Une fois que vous avez toutes les permutations, vous pouvez les lier avec les groupements si nécessaire.

Answer 3

J'ai rapidement fouetté du code pour cela. Cependant, j'ai omis de séparer chaque combinaison possible de la liste donnée, parce que je n'étais pas sûr que c'était réellement nécessaire, mais il devrait être facile à ajouter, si nécessaire. Quoi qu'il en soit, le code fonctionne assez bien pour de petites quantités, mais comme le mentionne déjà CodeByMoonlight, la quantité de possibilités est vraiment très élevée et le temps d'exécution augmente en conséquence.

Quoi qu'il en soit, voici le code python:

import time 

def separate(toseparate): 
    "Find every possible way to separate a given list." 
    #The list of every possibility 
    possibilities = [] 
    n = len(toseparate) 
    #We can distribute n-1 separations in the given list, so iterate from 0 to n 
    for i in xrange(n): 
    #Create a copy of the list to avoid modifying the already existing list 
    copy = list(toseparate) 
    #A boolean list indicating where a separator is put. 'True' indicates a separator 
    #and 'False', of course, no separator. 
    #The list will contain i separators, the rest is filled with 'False' 
    separators = [True]*i + [False]*(n-i-1) 
    for j in xrange(len(separators)): 
     #We insert the separators into our given list. The separators have to 
     #be between two elements. The index between two elements is always 
     #2*[index of the left element]+1. 
     copy.insert(2*j+1, separators[j]) 
    #The first possibility is, of course, the one we just created 
    possibilities.append(list(copy)) 
    #The following is a modification of the QuickPerm algorithm, which finds 
    #all possible permutations of a given list. It was modified to only permutate 
    #the spaces between two elements, so it finds every possibility to insert n 
    #separators in the given list. 
    m = len(separators) 
    hi, lo = 1, 0 
    p = [0]*m 
    while hi < m: 
     if p[hi] < hi: 
     lo = (hi%2)*p[hi] 
     copy[2*lo+1], copy[2*hi+1] = copy[2*hi+1], copy[2*lo+1] 
     #Since the items are non-unique, some possibilities will show up more than once, so we 
     #avoid this by checking first. 
     if not copy in possibilities: 
      possibilities.append(list(copy)) 
     p[hi] += 1 
     hi = 1 
     else: 
     p[hi] = 0 
     hi += 1 
    return possibilities 

t1 = time.time() 
separations = separate([2, 3, 3, 5]) 
print time.time()-t1 
sepmap = {True:"|", False:""} 
for a in separations: 
    for b in a: 
    if sepmap.has_key(b): 
     print sepmap[b], 
    else: 
     print b, 
    print "\n", 

Il est basé sur l'algorithme de QuickPerm, que vous pouvez en savoir plus sur ici: QuickPerm

Fondamentalement, mon code génère une liste contenant des séparations n, inserts dans la liste donnée, puis trouve toutes les permutations possibles des séparations dans la liste.

Donc, si nous utilisons votre exemple, nous obtenons:

2 3 3 5 
2 | 3 3 5 
2 3 | 3 5 
2 3 3 | 5 
2 | 3 | 3 5 
2 3 | 3 | 5 
2 | 3 3 | 5 
2 | 3 | 3 | 5 

En ,000154972076416 secondes. Cependant, j'ai lu la description du problème que vous faites et je vois comment vous essayez de résoudre cela, mais vu la rapidité avec laquelle le temps d'exécution augmente, je ne pense pas que cela fonctionnerait aussi vite que prévu. . Rappelez-vous que les problèmes du projet Euler devraient résoudre dans environ une minute.

Answer 4

En général, je regarderais la structure de la récursion utilisée pour calculer le nombre de configurations et générer une récursion similaire pour les énumérer. Le mieux est de calculer une correspondance un-à-un entre les entiers et les configurations. Cela fonctionne bien pour les permutations, les combinaisons, etc. et garantit que chaque configuration est énumérée une seule fois.

Maintenant, même le recursion for the number of partitions of some identical items est plutôt compliqué.

Pour les partitions de multisets, le comptage revient à résoudre la généralisation de Project Euler problem 181 à des multisets arbitraires.

Answer 5

Jetez un oeil à:

The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions

7.2.1.5. Génération toutes les partitions ensemble

Answer 6

Voici le code dont vous avez besoin pour cette partie de votre problème:

def memoize(f): 
    memo={} 
    def helper(x): 
     if x not in memo: 
      memo[x]=f(x) 
     return memo[x] 
    return helper 

@memoize 
def A000041(n): 
    if n == 0: return 1 
    S = 0 
    J = n-1 
    k = 2 
    while 0 <= J: 
     T = A000041(J) 
     S = S+T if k//2%2!=0 else S-T 
     J -= k if k%2!=0 else k//2 
     k += 1 
    return S 

print A000041(100) #the 100's number in this series, as an example