Faz um loop através de diferentes conjuntos de permutações exclusivas

9

Estou com dificuldades para começar a criar código de layout para esse problema.

Eu tenho uma quantidade fixa de números aleatórios, neste caso, 8 números. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Isso será colocado em 3 conjuntos de números, com a única restrição de que cada conjunto contenha um valor mínimo e cada valor só possa ser usado uma vez. Edit: todos os 8 números devem ser usados

Por exemplo:

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

Eu preciso percorrer todas as combinações possíveis de um conjunto R1, R2, R3. A ordem não é importante, por isso, se o exemplo acima aconteceu, não preciso de

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

O que é um bom método?

    
por user558610 31.12.2010 в 06:50
fonte

4 respostas

3

Tenho à minha frente Knuth Volume 4, Fascicle 3, Gerando todas as combinações e partições , seção 7.2.1.5 Gerando todas as partições definidas (página 61 no fascículo) .

Primeiro ele detalha o Algoritmo H, Strings de crescimento restrito em ordem lexicográfica devido a George Hutchinson. Parece simples, mas não vou mergulhar agora.

Na próxima página, sob uma elaboração Códigos de Gray para partições definidas , ele pondera:

  

Suponha, no entanto, que não estamos interessados em todas das partições; podemos querer apenas os que têm blocos m . Podemos fazer isso através da menor coleção de strings de crescimento restrito, ainda mudando um dígito de cada vez?

Depois ele detalha uma solução devido a Frank Ruskey.

A solução simples (e certa de estar correta) é codificar a filtragem do Algoritmo H em partições em que m==3 e nenhuma das partições são o conjunto vazio (de acordo com suas restrições declaradas). Eu suspeito que o Algoritmo H é extremamente rápido, então o custo de filtragem não será grande.

Se você estiver implementando isso em um 8051, você pode começar com o algoritmo Ruskey e filtrar apenas as partições que contêm o conjunto vazio.

Se você estiver implementando isso em algo menor que um 8051 e milissegundos importados, você poderá propagar cada uma das três partições com um elemento exclusivo (um loop aninhado simples de três níveis) e, em seguida, aumentar particionando nos cinco restantes elementos para m==3 usando o algoritmo Ruskey. Você não precisará filtrar nada, mas precisa controlar quais cinco elementos permanecem na partição.

A coisa boa sobre filtrar do algoritmo geral é que você não precisa verificar qualquer habilidade de sua preferência, e você muda de idéia mais tarde sobre suas restrições sem ter que revisar sua esperteza.

Eu posso até trabalhar uma solução mais tarde, mas isso é tudo por agora.

P.S. Para os guppies Java: Descobri a pesquisa em "George Hutchison restringiu as strings de crescimento" de um determinado pacote ca.ubc.cs.kisynski.bell com a documentação do método growthStrings () que implementa o algoritmo Hutchison.

Parece estar disponível no link

    
por Allan Stokes 01.01.2011 / 01:50
fonte
1

Provavelmente não é a melhor abordagem, mas deve funcionar.

Determine o número de combinações de três números que somam 8:

1,1,6
1,2,5
1,3,4
2,2,4
2,3,3

Para encontrar o acima, comecei com:

6,1,1 then subtracted 1 from six and added it to the next column...
5,2,1 then subtracted 1 from second column and added to next column...
5,1,2 then started again at first column...
4,2,2 carry again from second to third
4,1,3 again from first...
3,2,3 second -> third
3,1,4 

sabendo que menos da metade é 2, todas as combinações devem ter sido encontradas ... mas como a lista não é longa, é melhor irmos até o fim.

Agora classifique cada lista de 3 do maior para o menor (ou vice-versa) Agora, classifique cada lista de 3 em relação uma à outra. Copie cada lista exclusiva em uma lista de listas exclusivas. Agora temos todas as combinações que adicionam a 8 (cinco listas eu acho).

Agora, considere uma lista no conjunto acima

6,1,1 todas as combinações possíveis são encontradas por:

8 escolha 6, (já que escolhemos seis há apenas 2 para escolher) 2 pick 1, 1 pick 1 que funciona para 28 * 2 * 1 = 56, vale a pena saber quantas possibilidades existem para que você possa testar.

n escolha r (escolha r elementos de n opções totais)

n C r = n! / [(n-r)! r!]

Então, agora você tem o número total de iterações para cada componente da lista, pois o primeiro é 28 ...

O fato de escolher 6 itens de 8 é o mesmo que criar uma lista de 8 menos 2 elementos, mas quais dois elementos?

Bem, se removermos 1,2, isso nos deixa com 3,4,5,6,7,8. Vamos considerar todos os grupos de 2 ... Começando com 1,2 o próximo seria 1,3 ... então o seguinte é lido coluna por coluna.

12
13 23 
14 24 34
15 25 35 45
16 26 36 46 56
17 27 37 47 57 67
18 28 38 48 58 68 78

A soma de cada uma das colunas acima nos dá 28. (então isso cobriu apenas o primeiro dígito da lista (6,1,1), repita o procedimento para o segundo dígito (a um) que é "2 Choose 1". da esquerda em cima de dois dígitos da lista acima nós escolhemos um de dois e então para o último nós escolhemos o outro.

Eu sei que este não é um algoritmo detalhado, mas espero que você possa começar.

    
por Quaternion 31.12.2010 / 08:24
fonte
1

Transforme o problema em sua cabeça e você encontrará uma solução direta. Você tem 8 números que cada um precisa ser atribuído a exatamente um grupo; A "solução" é apenas uma solução se pelo menos um número for atribuído a cada grupo.

A implementação trivial envolveria 8 loops for e alguns IFs (pseudocódigo):

for num1 in [1,2,3]
  for num2 in [1,2,3]
    for num3 in [1,2,3]
      ...
        if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3))
          Print Solution!

Ele também pode ser implementado recursivamente, usando dois arrays e algumas funções. Muito melhor e mais fácil de depurar / seguir (pseudocódigo):

numbers = [1, 2, 3, 4, 5, 6, 7, 8]
positions = [0, 0, 0, 0, 0, 0, 0, 0]

function HandleNumber(i) {
  for position in [1,2,3] {
    positions[i] = position;
    if (i == LastPosition) {
        // Check if valid solution (it's valid if we got numbers in all groups)
        // and print solution!
      }
    else HandleNumber(i+1)
  }      
}

A terceira implementação não usaria nenhuma recursão e um pouco de retrocesso. Pseudocódigo, novamente:

numbers = [1,2,3,4,5,6,7,8]
groups = [0,0,0,0,0,0,0,0]

c_pos = 0 // Current position in Numbers array; We're done when we reach -1
while (cpos != -1) {
  if (groups[c_pos] == 3) {
      // Back-track
      groups[c_pos]=0;
      c_pos=c_pos-1
    }
  else {
     // Try the next group
     groups[c_pos] = groups[c_pos] + 1
     // Advance to next position OR print solution
     if (c_pos == LastPostion) {
         // Check for valid solution (all groups are used) and print solution!
       }
     else
       c_pos = c_pos + 1
    }
}
    
por Cosmin Prund 01.01.2011 / 17:29
fonte
0

Gere todas as combinações de subconjuntos recursivamente da maneira clássica. Quando você atingir o ponto em que o número de elementos restantes é igual ao número de subconjuntos vazios, restrinja-se apenas aos subconjuntos vazios.

Aqui está uma implementação do Python:

def combinations(source, n):
  def combinations_helper(source, subsets, p=0, nonempty=0):
    if p == len(source):
      yield subsets[:]
    elif len(source) - p == len(subsets) - nonempty:
      empty = [subset for subset in subsets if not subset]
      for subset in empty:
        subset.append(source[p])
        for combination in combinations_helper(source, subsets, p+1, nonempty+1):
          yield combination
        subset.pop()
    else:
      for subset in subsets:
        newfilled = not subset
        subset.append(source[p])
        for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled):
          yield combination
        subset.pop()

  assert len(source) >= n, "Not enough items"
  subsets = [[] for _ in xrange(n)]
  for combination in combinations_helper(source, subsets):
    yield combination

E um teste:

>>> for combination in combinations(range(1, 5), 2):
...   print ', '.join(map(str, combination))
... 
[1, 2, 3], [4]
[1, 2, 4], [3]
[1, 2], [3, 4]
[1, 3, 4], [2]
[1, 3], [2, 4]
[1, 4], [2, 3]
[1], [2, 3, 4]
[2, 3, 4], [1]
[2, 3], [1, 4]
[2, 4], [1, 3]
[2], [1, 3, 4]
[3, 4], [1, 2]
[3], [1, 2, 4]
[4], [1, 2, 3]
>>> len(list(combinations(range(1, 9), 3)))
5796
    
por marcog 31.12.2010 / 08:58
fonte