Comment générer une liste des sous-ensembles avec des restrictions?

Question

Je suis en train de trouver un algorithme efficace pour prendre une liste d'éléments et de générer tous les sous-ensembles uniques qui résultent de diviser la liste en exactement 2 sous-listes. Je suis sûr qu'il ya un moyen d'usage général pour ce faire, mais je suis intéressé par un cas particulier. Ma liste sera triée, et il peut y avoir des éléments en double.

Voici quelques exemples:

Entrée
{1,2,3}

Sortie
{{1}, {2,3}}
{{2}, {1,3}}
{{3}, {1,2}}

Entrée
{1,2,3,4}

Sortie
{{1}, {2,3,4}}
{{2}, {1,3,4}}
{{3}, {1,2,4}}
{{4}, {1,2,3}}
{{1,2}, {3,4}}
{{1,3}, {2,4}}
{{1,4}, {2,3}}

Entrée
{1,2,2,3}

Sortie
{{1}, {2,2,3}}
{{2}, {1,2,3}}
{{3}, {1,2,2}}
{{1,2}, {2,3}}
{{1,3}, {2,2}}

Je peux le faire sur le papier, mais je me bats pour trouver un moyen simple de le faire par programme. Je cherche seulement une description rapide de pseudocode comment faire, pas des exemples de code spécifique.

Toute aide est appréciée. Merci.

Answer 1

La fonction suivante C ++ fait exactement ce dont vous avez besoin, mais l'ordre est différent de celui dans les exemples:

// input contains all input number with duplicates allowed
void generate(std::vector<int> input) {
  typedef std::map<int,int> Map;
  std::map<int,int> mp;
  for (size_t i = 0; i < input.size(); ++i) {
    mp[input[i]]++;
  }

  std::vector<int> numbers;
  std::vector<int> mult;
  for (Map::iterator it = mp.begin(); it != mp.end(); ++it) {
    numbers.push_back(it->first);
    mult.push_back(it->second);
  }

  std::vector<int> cur(mult.size());
  for (;;) {
    size_t i = 0;
    while (i < cur.size() && cur[i] == mult[i]) cur[i++] = 0;
    if (i == cur.size()) break;
    cur[i]++;
    std::vector<int> list1, list2;
    for (size_t i = 0; i < cur.size(); ++i) {
      list1.insert(list1.end(), cur[i], numbers[i]);
      list2.insert(list2.end(), mult[i] - cur[i], numbers[i]);
    }
    if (list1.size() == 0 || list2.size() == 0) continue;
    if (list1 > list2) continue;
    std::cout << "{{";
    for (size_t i = 0; i < list1.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list1[i];
    }
    std::cout << "},{";
    for (size_t i = 0; i < list2.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list2[i];
    }
    std::cout << "}\n";
  }
}

Answer 2

Si vous généraient tous les sous-ensembles vous finiriez générer 2 ⁿ sous-ensembles pour une liste de longueur n . Une façon courante de le faire est d'itérer à travers tous les numéros i de 0 à 2 ⁿ -1 et en utilisant les bits qui sont définis dans i pour déterminer quels éléments sont dans le i e sous-ensemble. Cela fonctionne parce que tout élément est soit présent ou non dans un sous-ensemble particulier, donc par itérer toutes les combinaisons de n Mèches vous itérer le 2 ⁿ sous-ensembles.

Par exemple, pour générer les sous-ensembles de (1, 2, 3) vous itérer les numéros 0 à 7:

  

0 = 000 _b → ()
  1 = 001 _b → (1)
  2 = 010 _b → (2)
  3 = 011 _b → (1, 2)
  4 = 100 _b → (3)
  5 = 101 _b → (1, 3)
  6 = 110 _b → (2, 3)
  7 = 111 _b → (1, 2, 3)

Dans votre problème, vous pouvez générer chaque sous-ensemble et son complément pour obtenir votre paire de sous-ensembles mutuellement exclusifs. Chaque paire sera répété lorsque vous faites cela pour que vous ne devez itérer jusqu'à 2 ^{n -1} -. 1 puis arrêter

  

1 = 001 _b → (1) + (2, 3)
  2 = 010 _b → (2) + (1, 3)
  3 = 011 _b → (1, 2) + (3)

Pour traiter les doublons vous pouvez générer des sous-ensembles d'indices de liste au lieu de sous-ensembles d'éléments de liste. Comme avec la liste (1, 2, 2, 3) générer des sous-ensembles de la liste (0, 1, 2, 3) au lieu, puis utiliser ces chiffres comme indices dans le (1, 2, 2, 3) liste. Ajouter un niveau d'indirection, essentiellement.

Voici un code Python mettant tout cela ensemble.

#!/usr/bin/env python

def split_subsets(items):
    subsets = set()

    for n in xrange(1, 2 ** len(items) / 2):
        # Use ith index if ith bit of n is set.
        l_indices = [i for i in xrange(0, len(items)) if n & (1 << i) != 0]
        # Use the indices NOT present in l_indices.
        r_indices = [i for i in xrange(0, len(items)) if i not in l_indices]

        # Get the items corresponding to the indices above.
        l = tuple(items[i] for i in l_indices)
        r = tuple(items[i] for i in r_indices)

        # Swap l and r if they are reversed.
        if (len(l), l) > (len(r), r):
            l, r = r, l

        subsets.add((l, r))

    # Sort the subset pairs so the left items are in ascending order.
    return sorted(subsets, key = lambda (l, r): (len(l), l))

for l, r in split_subsets([1, 2, 2, 3]):
    print l, r

Sortie:

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

Answer 3

Un peu de code Erlang, le problème est qu'il génère des doublons lorsque vous avez des éléments en double, de sorte que la liste des résultats doit encore filtrer ...

do([E,F]) -> [{[E], [F]}];
do([H|T]) -> lists:flatten([{[H], T}] ++
                           [[{[H|L1],L2},{L1, [H|L2]}]  || {L1,L2} <- all(T)]).

filtered(L) ->
  lists:usort([case length(L1) < length(L2) of true -> {L1,L2};
                                               false -> {L2,L1} end
              || {L1,L2} <- do(L)]).

pseudocode cela signifie que:

• pour une longue liste de deux {E, F} est le résultat {{e}, {F}}
• pour des listes plus longues de prendre le premier élément H et le reste de la liste et le retour T
  • {{H}, {T}} (le premier élément sous forme de liste d'élément unique, et la liste restante)
  • exécuter aussi l'algorithme récursif pour T, et pour chaque {L1, L2} élément dans la liste résultante retour {{H, L1}, {L2}} et {{L1}, {H, L2}}

Answer 4

Ma suggestion est ...

D'abord, comptez combien de chaque valeur que vous avez, peut-être dans un Hashtable. Ensuite, calculer le nombre total de combinaisons à considérer -. Le produit des comptes

itérer ce nombre de combinaisons.

A chaque combinaison, copiez votre nombre de boucles (comme x), puis lancez une boucle intérieure à travers vos articles Hashtable.

Pour chaque élément Hashtable, utilisez (x modulo nombre) comme nombre d'instances de la clé Hashtable dans la première liste. Diviser x par le nombre avant de répéter la boucle interne.

Si vous craignez que le nombre de combinaisons peut déborder votre type entier, la question est évitable. Utiliser un tableau pour chaque article (une pour chaque touche hashmap) à partir de zéro, et « nombre » dans les combinaisons de traitement de chaque élément de matrice comme un chiffre (si la totalité du tableau représente le numéro de la combinaison), mais avec chaque « chiffre » ayant une autre base (le comptage correspondant). Autrement dit, à « augmentation » du tableau, premier élément d'incrément 0. Si elle déborde (devient égal à son compte), fixé à zéro et incrémenter l'élément suivant du tableau. Répétez les contrôles de débordement jusqu'à ce que si les débordements continuent après la fin du tableau, vous avez terminé.

Je pense que sergdev utilise une approche très similaire à ce second, mais en utilisant std :: carte plutôt que d'une table de hachage (std :: unordered_map devrait fonctionner). Un Hashtable devrait être plus rapide pour un grand nombre d'articles, mais ne vous donnera pas les valeurs dans un ordre particulier. La commande pour chaque boucle à travers les clés dans une table de hachage doit être cohérente, cependant, à moins que ajouter / supprimer des clés.