Come generare un elenco di sottoinsiemi con restrizioni?

Question

Sto cercando di trovare un algoritmo efficiente per prendere un elenco di elementi e generare tutti i sottoinsiemi univoci risultanti dalla divisione dell'elenco esattamente in 2 sottoelenchi.Sono sicuro che esiste un modo generale per farlo, ma sono interessato a un caso specifico.Il mio elenco verrà ordinato e potrebbero essere presenti elementi duplicati.

Qualche esempio:

Ingresso
{1,2,3}

Produzione
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

Ingresso
{1,2,3,4}

Produzione
{{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}}

Ingresso
{1,2,2,3}

Produzione
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2,3}}
{{1,3},{2,2}}

Posso farlo su carta, ma faccio fatica a trovare un modo semplice per farlo a livello di codice.Sto solo cercando una breve descrizione in pseudocodice su come eseguire questa operazione, non esempi di codice specifici.

Qualsiasi aiuto è apprezzato.Grazie.

Answer 1

La seguente funzione C ++ fa esattamente quello che ti serve, ma l'ordine è diverso da quello negli esempi:

// 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

Se si stavano generando tutti i sottoinsiemi si finirebbe per generare 2 ⁿ sottoinsiemi per una lista di lunghezza n . Un modo comune per farlo è per scorrere tutti i numeri i da 0 a 2 ⁿ -1 e utilizzare i bit impostati in i per determinare quali elementi sono in i esimo sottoinsieme. Questo funziona perché ogni elemento è o non è presente in un particolare sottoinsieme, quindi scorrendo tutte le combinazioni di n i bit di eseguire iterazioni sulle 2 ⁿ sottoinsiemi.

Ad esempio, per generare i sottoinsiemi di (1, 2, 3) si dovrebbe scorrere i numeri da 0 a 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)

Nel vostro problema è possibile generare ogni sottoinsieme e il suo complemento per ottenere il vostro paio di sottoinsiemi si escludono a vicenda. Ciascuna coppia si sarebbe ripetuto quando si esegue questa operazione in modo che solo bisogno di iterare fino a 2 ^{n -1} -. 1 e poi fermarsi

  

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

Per affrontare gli elementi duplicati si potrebbe generare sottoinsiemi di indici delle liste, invece di sottoinsiemi di voci di elenco. Come con l'elenco (1, 2, 2, 3) generare sottoinsiemi della lista (0, 1, 2, 3), invece, e quindi utilizzare quei numeri come indici in (1, 2, 2, 3) lista. Aggiungere un livello di indirezione, in pratica.

Ecco un po 'di codice Python mettere tutto questo insieme.

#!/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

Output:

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

Answer 3

Un po 'di codice di Erlang, il problema è che esso genera duplicati quando si dispone di elementi duplicati, quindi l'elenco dei risultati ha ancora bisogno di essere filtrata ...

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

in pseudocodice questo significa che:

• per una lunga lista di due {E, F} il risultato è {{E}, {F}}
• per le liste più prendere il primo elemento H e il resto della lista T e ritorno
  • {{H}, {T}} (il primo elemento come un unico elemento elenco, e l'elenco rimanente)
  • anche eseguire l'algoritmo ricorsivo per T, e per ciascun elemento {L1, L2} nell'elenco ritorno risultante {{H, L1}, {L2}} e {{L1}, {H, L2}}

Answer 4

Il mio suggerimento è...

Innanzitutto, conta quanti valori hai, possibilmente in una tabella hash.Quindi calcola il numero totale di combinazioni da considerare: il prodotto dei conteggi.

Ripetere quel numero di combinazioni.

Ad ogni combinazione, copia il conteggio del ciclo (come x), quindi avvia un ciclo interno attraverso gli elementi della tabella hash.

Per ogni elemento della tabella hash, utilizza (x modulo count) come numero di istanze della chiave hash nel primo elenco.Dividi x per il conteggio prima di ripetere il ciclo interno.

Se temi che il numero di combinazioni possa eccedere il tuo tipo intero, il problema è evitabile.Utilizzare un array con ciascun elemento (uno per ogni chiave hashmap) a partire da zero e "contare" attraverso le combinazioni trattando ciascun elemento dell'array come una cifra (in modo che l'intero array rappresenti il ​​numero della combinazione), ma con ciascuna "cifra" avente un base diversa (il conteggio corrispondente).Cioè, per "incrementare" l'array, incrementare prima l'elemento 0.Se eccede (diventa uguale al suo conteggio), impostalo su zero e incrementa l'elemento successivo dell'array.Ripetere i controlli di overflow finché Se gli overflow continuano oltre la fine dell'array, non avete finito.

Penso che sergdev stia utilizzando un approccio molto simile a questo secondo, ma utilizzando std::map anziché una tabella hash (std::unordered_map dovrebbe funzionare).Una tabella hash dovrebbe essere più veloce per un numero elevato di elementi, ma non fornirà i valori in un ordine particolare.Tuttavia, l'ordine per ogni ciclo delle chiavi in ​​una tabella hash dovrebbe essere coerente, salvo che aggiungi/rimuovi chiavi.