Como gerar uma lista de subconjuntos com restrições?

Question

Estou tentando descobrir um algoritmo eficiente para pegar uma lista de itens e gerar todos os subconjuntos exclusivos que resultam da divisão da lista em exatamente 2 sublistas. Tenho certeza de que existe uma maneira de propósito geral de fazer isso, mas estou interessado em um caso específico. Minha lista será classificada e pode haver itens duplicados.

Alguns exemplos:

Entrada
{1,2,3}

Resultado
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

Entrada
{1,2,3,4}

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

Entrada
{1,2,2,3}

Resultado
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2,3}}
{{1,3},{2,2}}

Eu posso fazer isso no papel, mas estou lutando para descobrir uma maneira simples de fazê -lo programaticamente. Estou procurando apenas uma descrição rápida do pseudocódigo de como fazer isso, não nenhum exemplo de código específico.

Qualquer ajuda é apreciada. Obrigado.

Answer 1

A função C ++ a seguir faz exatamente o que você precisa, mas a ordem difere daquele em exemplos:

// 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 você estivesse gerando todos os subconjuntos, acabaria gerando 2ⁿ subconjuntos para uma lista de comprimento n. Uma maneira comum de fazer isso é iterar em todos os números eu de 0 a 2ⁿ-1 e use os bits que são definidos eu para determinar quais itens estão no euo subconjunto. Isso funciona porque qualquer item está ou não está presente em nenhum subconjunto em particular; portanto, iterando todas as combinações de n Bits você itera através do 2ⁿ subconjuntos.

Por exemplo, para gerar os subconjuntos de (1, 2, 3), você itera através dos números de 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)

No seu problema, você pode gerar cada subconjunto e seu complemento para obter seu par de subconjuntos mutuamente exclusivos. Cada par seria repetido quando você fizer isso, então você só precisa iterar até 2^n-1 - 1 e depois pare.

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

Para lidar com itens duplicados, você pode gerar subconjuntos de índices de lista em vez de subconjuntos de itens de lista. Como na lista (1, 2, 2, 3), geram subconjuntos da lista (0, 1, 2, 3) e, em seguida, use esses números como índices na lista (1, 2, 2, 3). Adicione um nível de indireção, basicamente.

Aqui está algum código Python juntando tudo isso.

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

Resultado:

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

Answer 3

Um pouco de código Erlang, o problema é que ele gera duplicatas quando você tem elementos duplicados, para que a lista de resultados ainda precise ser filtrada ...

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

No pseudocódigo, isso significa que:

• Para uma lista de dois longos {e, f}, o resultado é {{e}, {f}}
• Para listas mais longas, pegue o primeiro elemento H e o restante da lista T e retorne
  • {{H}, {t}} (o primeiro elemento como uma única lista de elementos e a lista restante)
  • Execute também o algoritmo recursivamente para T, e para cada elemento {L1, L2} na lista resultante retorna {{h, l1}, {l2}} e {{l1}, {h, l2}}

Answer 4

Minha sugestão é ...

Primeiro, conte quantos de cada valor você tem, possivelmente em uma hashtable. Em seguida, calcule o número total de combinações a serem consideradas - o produto das contagens.

Itera através desse número de combinações.

Em cada combinação, copie sua contagem de loop (como x) e inicie um loop interno através de seus itens de hashtable.

Para cada item de hashtable, use (x contagem de módulos) como seu número de instâncias da chave de hashtable na primeira lista. Divida X pela contagem antes de repetir o loop interno.

Se você está preocupado que o número de combinações possa transbordar seu tipo inteiro, o problema é evitável. Use uma matriz com cada item (um para cada chave de hashmap) a partir de zero e 'contagem' através das combinações que tratam cada item da matriz como um dígito (para que toda a matriz represente o número de combinação), mas com cada 'dígito' com um Base diferente (a contagem correspondente). Isto é, para 'incrementar' a matriz, o primeiro Item de Incremento 0. Se ele transbordar (se tornar igual à sua contagem), defina -o para zero e incrementar o próximo item da matriz. Repita as verificações de transbordamento até que, se os transbordamentos continuarem além do final da matriz, você terminou.

Eu acho que o Sergdev está usando uma abordagem muito semelhante a este segundo, mas usando o mapa STD :: em vez de um hashtable (std :: unorded_map deve funcionar). Um hashtable deve ser mais rápido para um grande número de itens, mas não fornecerá os valores em qualquer ordem específica. A ordem para cada loop através das chaves em um hashtable deve ser consistente, no entanto, a não ser que Você adiciona/remove as teclas.