Algorithme efficace pour «résumer» un ensemble de sommes

24

Étant donné un ensemble multiple de nombres naturels X, considérons l'ensemble de toutes les sommes possibles:

sums(X)={iAi|AX}

Par exemple, sums({1,5})={0,1,5,6} tandis que sums({1,1})={0,1,2} .

Quel est l'algorithme le plus efficace pour calculer l'opération inverse (mesurée en termes de taille de l'ensemble d'entrée de sommes)? Plus précisément, il est possible de calculer efficacement l'un des éléments suivants:

  1. Si un ensemble donné est un ensemble valide de sommes. (Par exemple, {0,1,2} est valide mais {0,1,3} ne l'est pas.)
  2. Un multiset qui résume à l'ensemble donné.
  3. Le plus petit multiset qui correspond à l'ensemble donné. (Par exemple, {1,2} et {1,1,1} tous les deux à {0,1,2,3} mais le premier est plus petit.)
Uri Granta
la source
1
Pourriez-vous éventuellement nous donner le multi - ensemble de sommes plutôt que l' ensemble de sommes? Cela créerait une symétrie agréable (vu que vous commencez avec un multi-ensemble de valeurs).
DW
1
Une autre question - êtes-vous le plus intéressé par les résultats théoriques (par exemple, la complexité asymptotique), ou les solutions pratiques (schémas qui pourraient fonctionner correctement dans la pratique)? Dans ce dernier cas, avez-vous une idée des valeurs typiques des paramètres: par exemple, la taille du multiset X, la taille du plus grand élément du multiset X, la multiplicité la plus élevée? Cela peut affecter s'il est raisonnable d'appliquer un «gros marteau» comme un solveur ILP ou un solveur SAT.
DW
@DW Je suis vraiment intéressé à utiliser l'ensemble des sommes plutôt que le multiset (bien que cela puisse aussi être un problème intéressant). De plus, c'était à l'origine un problème de mathématiques récréatives, donc je m'intéresse principalement aux limites de la complexité plutôt qu'à une solution pratique.
Uri Granta
3
Si vous disposez du multi-ensemble de sommes, il est assez simple de le faire avec gourmandise (voir par exemple math.stackexchange.com/questions/201545/… ).
jschnei
@UriZarfaty l'ensemble donné en entrée est déjà trié? Enfin, cela est défini ou multiset? Le commentaire suggère toujours que vous voulez un ensemble pur.
Evil

Réponses:

9

Solution

La solution comprend deux parties. Nous découvrons d'abord un ensemble minimal, puis nous prouvons qu'il peut représenter l'ensemble de la puissance. La solution est ajustée pour la mise en œuvre de la programmation.

Algorithme d'ensemble minimal

  1. Trouvez l'élément maximal dans l'ensemble (multi) de somme. P , l'ensemble minimal (multi) potentiel est initialement vide.amP

  2. À moins qu'il n'y ait qu'un seul groupe, représenter de toutes les manières possibles comme une paire de sommes qui s'additionnent à un m , S i j = { ( a i , a j ) | a i + a j = a m }amamSij={(ai,aj)|ai+aj=am}

  3. Vérifiez que tous les éléments de l'ensemble des sommes sont inclus.

  4. Trouver élément maximal de tous les S i j ( ce qui signifie ensemble) avec la propriété suivante: pour chaque S i j , un s est soit en S i j , ou nous pouvons trouver un p de l'ensemble des sommes ainsi que d' un p + a s est dans S i j .asSijSijasSijapap+asSij

  5. Si tel est le cas que ne contient pas un s , juste la somme d' un s + un p , supprimer un p + a s de S i j (ou tout simplement mettre une marque de l' ignorer) et insérer un p et un s dans S i j à la place.Sijasas+apap+asSijapasSij

  6. Si un élément est présent dans tous les le retirer de tous les S i j une fois (ou tout simplement mettre une marque de l' ignorer et de ne pas toucher plus longtemps) et l' ajouter à la liste des éléments de l' ensemble minimal potentiel P .SijSijP

  7. Répétez jusqu'à ce que tous les soient videsSij

  8. Si une partie de reste non vide et que nous ne pouvons pas continuer, essayez à nouveau avec la valeur maximale de toutes les S i j .SijSij

  9. Recréer les étapes récursives sans le transfert et continuer avec l' algorithme de couverture du jeu de pouvoir sur . (Avant cela, vous pouvez vérifier que P inclut tous les éléments qui ne peuvent pas être représentés comme une somme de deux éléments, ils doivent donc être dans l'ensemble sous-jacent à coup sûr. Par exemple, l'élément minimal doit être dans P. )PPP

(10. Notez qu'une solution d'ensemble minimale qui est le but de l'algorithme ne peut pas contenir plus d'une répétition du même nombre.)

Exemple:

{2,3,5,7,8,10,12,13,15}

Représentez 15 de toutes les manières possibles comme une somme de deux nombres de l'ensemble des sommes.

(13,2),(12,3),(10,5),(8,7)

Essayez de trouver le nombre maximal qui est dans tous les groupes ou qui peut être représenté comme une somme. Évidemment, nous pouvons commencer à le rechercher à partir de 8, il est inutile de le dépasser.

13 du premier groupe est 13 = 8 + 5 donc 13 est bien, mais 12 du deuxième groupe n'est pas bien car il n'y a pas de 4 pour faire 12 = 8 + 4 dans l'ensemble des sommes. Ensuite, nous essayons avec 7. Mais immédiatement 13 ne peuvent pas être couverts, il n'y en a pas 6.

Ensuite, nous essayons 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, et pour le dernier soit 8 = 5 + 3 ou 7 = 5 + 2 mais pas les deux. Les groupes sont désormais:

((5,8),2),((5,7),3),((5,5),5),((5,3),7)

5 se répète dans tous les groupes donc nous l'extrayons . Nous extrayons 5 une seule fois de chaque groupe.P={5}

(8,2),(7,3),(5,5),(3,7)

De toute évidence, il est inutile de dépasser 5, nous essayons donc à nouveau 5. 8 = 5 + 3, 7 = 5 + 2, donc tout va bien

((5,3),2),((5,2),3),(5,5),(3,(5,2))

Extrayez à nouveau un 5 de tous les groupes car il se répète. (Ce n'est pas courant mais notre cas est délibérément créé pour afficher ce qu'il faut faire au cas où nous aurions des répétitions.) P={5,5}

(3,2),(2,3),(5),(3,2)

Maintenant, nous essayons avec 3 et avons 5 = 3 + 2. Ajoutez-le au groupe.

(3,2),(2,3),(3,2),(3,2)

Maintenant, extrayez 3 et 2 car ils se répètent partout et nous allons bien et les groupes sont vides.P={5,5,3,2}

(),(),(),()

Maintenant, nous devons recréer des étapes récursives sans suppressions, cela signifie simplement faire ce qui précède sans vraiment supprimer les éléments de simplement en les plaçant dans P et en marquant pour ne plus les modifier.SijP

( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) , 7

(13,2),(12,3),(10,5),(8,7)
( ( 5 , ( 5 , 3 ) ) , 2 ) , ( ( 5 , ( 5 , 2 ) ) , 3 ) , ( ( 5 , ( 3 , 2 ) ) , 5 ) , ( ( 5 , 3 ) , ( 5 , 2 ) )
((5,8),2),((5,7),3),((5,5),5),((5,3),7)
((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))

Couverture de l'ensemble d'alimentation

Le but de cette partie est de vérifier si l'ensemble minimal trouvé est capable de couvrir l'ensemble de la somme de puissance. Il est possible qu'une solution trouvée puisse couvrir toutes les sommes données, mais qu'il ne s'agisse pas de sommes définies par la puissance. (Techniquement, vous pouvez simplement créer un ensemble de sommes de puissance à partir de l'ensemble minimal trouvé et vérifier si chaque somme, selon les exigences de l'ensemble de puissances, est dans l'ensemble de sommes initial. C'est tout ce qui vient de fusionner avec ce que nous avons déjà, donc rien n'est gaspillé Vous pouvez faire cette partie en rembobinant la récursivité.)

  1. Encodez tous les éléments de l'ensemble minimal en utilisant des puissances successives de 2. L'ordre n'est pas important. Encodez le même élément avec une nouvelle valeur autant de fois qu'il se répète. Partir de C = 1, chaque élément suivant a C = 2C.

(2=[1],3=[2],5=[4],5=[8])
  1. Remplacer les éléments de la liste de récursivité restaurée,

((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))

avec l'encodage: 2 avec 1, 3 avec 2, 5 avec 4 et 5 avec 8. Observez que chaque élément a un encodage différent même s'il est répété.

((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))
  1. Recueillir toutes les sommes intermédiaires, pour le moment (1,2,4,8)

((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))

(1,2,3,4,5,8,9,10)

((14),1),((13),2),((7),8),(15)

(1,2,3,4,5,8,9,10,13,14,15)

{(15),(15),(15),(15)}
  1. 2m1mm=4

  2. 12m1

(6,7,11,12)

  1. Justifiez leur absence de la manière suivante: représentez chaque nombre sous forme binaire

(6=01102) (7=01112) (11=10112) (12=10102)

601102(2=[1],3=[2],5=[4],5=[8]){2,3,5,7,8,10,12,13,15}, donc tout va bien.

701112(2=[1],3=[2],5=[4],5=[8])

1112

Si une représentation binaire correspond à la somme introuvable, signalez qu'il n'y a pas de solution.

(2,3,5,5)

Discussion

Il était nécessaire de fournir l'algorithme qui va vérifier si les sommes couvrent l'achèvement de l'ensemble de puissance, ce qui est caché dans l'expansion binaire. Par exemple, si nous excluons 8 et 7 de l'exemple initial, la première partie fournirait toujours la solution, seule la deuxième partie rapporterait les combinaisons de sommes manquantes.

mnlog(m)mlog2(m)mnlog(m)

mlogmmlog2(m)

mlog3(m)

Certaines parties de l'algorithme supposent que nous pouvons trouver la paire de sommes en temps linéaire et cela nécessite un tri.

Démarrage incorrect

2,3,4,5,6,7,8,9,10,11,12,13,152,3,4,6Sij

5,4,3,3

2,2,3,4,42,3,4,6

Le but de cet algorithme est de fournir une solution une fois que nous avons tout démarré correctement.

Améliorations

L'étape 4. est celle qui pourrait être améliorée de cette manière: au lieu de maximale, nous pourrions essayer chaque élément dans l'ordre décroissant qui satisfait la condition donnée. Nous créons une branche distincte pour chacun. Si une branche ne donne pas de solution, annulez-la.

2,3,4,5,6,7,8,9,10,11,12,13,157,6,5,4de manière distincte, car tous réussissent le premier test. (Il n'y a aucune raison d'utiliser 2 ou 3 car nous savons qu'ils doivent être dans l'ensemble sous-jacent.) Et continuez simplement de cette façon tout autour jusqu'à ce que nous collections toutes les versions pouvant atteindre la fin. Cela créerait une solution à couverture complète qui découvrirait plus d'un ensemble sous-jacent.

Une autre chose, puisque nous savons que nous ne pouvons pas avoir plus d'une répétition si le cas est minimal, nous pouvons l'incorporer dans notre algorithme.

Dans l'ensemble, la condition à l'étape 4. qu'un nombre doit se répéter dans chaque groupe ou avoir la capacité de créer une somme est assez forte pour nous sortir des eaux exponentielles directes, ce qui serait un algorithme d'essayer simplement chaque combinaison et de créer le pouvoir mis sur chacun jusqu'à ce que nous trouvons une correspondance.


la source
1
Plus largement: je vois une description textuelle d'un algorithme, mais (a) aucun pseudocode, et (b) aucune preuve d'exactitude. Pourquoi pensez-vous que cette approche fournit un algorithme qui fonctionnera correctement sur toutes les entrées possibles? Quelle est la justification? Avez-vous une preuve d'exactitude pour cela?
DW
Je pense que le problème a pris environ 30 heures de travail tous ensemble (30 fois le taux horaire, enfin ...). Mais il n'y a pas d'option payante.
Enfin, lisez la réponse dans le détail qu'elle méritait. Bon travail!
Uri Granta
1

REMARQUE: cela ne fonctionne pas tout à fait en général, voir le contre-exemple d'Uri ci-dessous.

YY

  • 0Y
  • yYyXY
  • z1<<znYYY=Y+{0,y}0Yi=1,,nzi+yYziYziyYzi+yYzi+yYziY
  • Yy,y,

1yO(n)O(n2)

Y={0,1,3,4,5,6,7}{0,1,3,4,6}{0,1,3,5,6}yY{a+ky}YY

Klaus Draeger
la source
Est-il évident que Y 'ne mène pas à une impasse? Après tout, il peut y avoir de nombreux Y tels que Y = Y '+ {0, y}. Par exemple {0,1,2,3,4} = {0,2,3} + {0,1} = {0,1,2,3} + {0,1} mais l'ancienne décomposition conduit à un impasse.
Uri Granta
C'est vrai et c'est un vrai problème. Je vais devoir voir si cela peut être corrigé. Merci!
Klaus Draeger
YkY=Y+{0,y,,y}{0,y,,y}kyY