Encontrar um conjunto de permutações, com uma restrição

Question

I tem um conjunto de N ^ 2 números e caixas N. Cada bin é suposto ter N números do conjunto atribuído a ele. O problema que estou enfrentando é encontrar um conjunto de distribuições que mapeiam os números para as caixas, satisfazendo a restrição, que cada par de números podem compartilhar a mesma bin apenas uma vez.

A distribuição pode muito bem ser representados por uma matriz NxN, em que cada linha representa um bin. Então o problema é encontrar um conjunto de permutações da matriz' elementos, em que cada par de números compartilha a mesma linha apenas uma vez. É irrelevante qual linha é, apenas que dois números foram atribuídos ao mesmo.

Exemplo 3 conjunto de permutações que satisfaça a restrição para N = 8:

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

 0  8 16 24 32 40 48 56
 1  9 17 25 33 41 49 57
 2 10 18 26 34 42 50 58
 3 11 19 27 35 43 51 59
 4 12 20 28 36 44 52 60
 5 13 21 29 37 45 53 61
 6 14 22 30 38 46 54 62
 7 15 23 31 39 47 55 63

 0  9 18 27 36 45 54 63
 1 10 19 28 37 46 55 56
 2 11 20 29 38 47 48 57
 3 12 21 30 39 40 49 58
 4 13 22 31 32 41 50 59
 5 14 23 24 33 42 51 60
 6 15 16 25 34 43 52 61
 7  8 17 26 35 44 53 62

Uma permutação que não pertence no conjunto acima:

 0 10 20 30 32 42 52 62
 1 11 21 31 33 43 53 63
 2 12 22 24 34 44 54 56
 3 13 23 25 35 45 55 57
 4 14 16 26 36 46 48 58
 5 15 17 27 37 47 49 59
 6  8 18 28 38 40 50 60
 7  9 19 29 39 41 51 61

Por causa de múltiplas colisões com o segundo permutação, uma vez que, por exemplo, ambos estão emparelhar os números 0 e 32 em uma linha.

---

Enumerando três é fácil, ele é composto por 1 permutação arbitrária, a sua transposição e uma matriz onde as linhas são feitas da matriz anterior' diagonais.

Não consigo encontrar uma maneira de produzir um conjunto constituído por mais embora. Parece ser um problema muito complexo, ou um problema simples com uma solução não óbvia. De qualquer maneira eu ficaria grato se alguém tinha alguma idéia de como resolvê-lo em tempo razoável para a N = 8 caso, ou identificado o nome próprio, acadêmico do problema, então eu poderia google para ele.

Em caso você estava pensando, o que é útil para, eu estou procurando um algoritmo de escalonamento para um crossbar switch com 8 buffers, que serve o tráfego para 64 destinos. Esta parte do algoritmo de escalonamento é agnóstico tráfego de entrada, e muda ciclicamente entre um número de destino mapeamentos-tampão com fio. O objetivo é fazer com que cada par de endereços de destino concorrer para o mesmo tampão apenas uma vez no período de ciclismo, e para maximizar a duração desse período. Em outras palavras, de modo que cada par de endereços foi compete para o mesmo tampão mais raramente possível.

---

EDIT:

Aqui está algum código que eu tenho. CÓDIGO

É ganancioso, ele geralmente termina depois de encontrar o terceiro permutação. Mas deve existir um conjunto de pelo menos n permutações que satisfazem o problema.

A alternativa exigiria que a escolha de permutação I envolvido procurando permutações (I + 1..N), para verificar se permutação I é parte da solução que consiste no número máximo de permutações. Isso iria requerer enumerar todas as permutações de verificar a cada passo, que é proibitivamente caro.

Answer 1

O que você quer é um combinatória blocos . Usando a nomenclatura na página ligada, você quer projetos de tamanho (n ^ 2, n, 1) para o máximo k. Isto lhe dará n (n + 1) permutações, usando a sua nomenclatura. Este é o máximo possível, teoricamente, por um argumento a contagem (ver a explicação no artigo para a derivação de b a partir de V, K, e lambda). Tais modelos existem para n = p ^ k para alguns primo p e inteiro k, usando um plano afim. Conjectura-se que os aviões única afins que existem são deste tamanho. Portanto, se você pode selecionar n, talvez esta resposta será suficiente.

No entanto, se em vez do máximo número possível teoricamente de permutações, você só quer encontrar um grande número (o mais que puder para um dado n ^ 2), eu não sei o que o estudo desses objetos é chamado.

Answer 2

Adicione uma matriz de 64 x 64 x 8: boleano proibido [i] [j] [k], que indica se o par (i, j) tem aparecido na linha k. Cada vez que utilizar o par (i, j) na linha k, vai definir o valor associado nesta matriz para um. Note que você só vai usar a metade desta matriz para a qual i

Para construir uma nova permutação, começar por tentar o membro 0, e verificar que pelo menos sete dos proibida [0] [j] [0] que são unset. não sete Se houver esquerda, incremento e tente novamente. Repita o procedimento para preencher o resto da linha. Repita esse processo todo para preencher toda a permutação NxN.

Há provavelmente otimizações você deve ser capaz de chegar a como você implementar isso, mas isso deve fazer muito bem.

Answer 3

Possivelmente você poderia reformular o seu problema em teoria dos grafos. Por exemplo, você começa com o gráfico completo com vértices N × N. Em cada passo, que particionar o gráfico em N N-cliques, e, em seguida, remover todas as arestas utilizado.

Para esta N = 8 caso, K64 tem 64 × 63/2 = 2,016 arestas e sessenta e quatro lotes de K8 têm 1792 bordas, para que o seu problema pode não ser impossível: -)

Answer 4

Right, o estilo gananciosos não funciona porque você correr para fora de números.

É fácil ver que não pode haver mais de 63 permutações antes de violar a restrição. No 64, você terá de emparelhar pelo menos um dos números com um outro seu já sido emparelhado com. O princípio da casa dos pombos.

Na verdade, se você usar a tabela de pares proibidos sugeri anteriormente, você encontrará que há um máximo de apenas N + 1 = 9 permutações possíveis antes de executar fora. A tabela tem N ^ x 2 (N ^ 2-1) / 2 = 2016 restrições não redundantes, e cada nova permutação criará N x (N escolher 2) = 28 novos emparelhamentos. Assim, todos os sorteios serão utilizados depois 2016/28 = 9 permutações. Parece que perceber que há tão poucas permutações é a chave para resolver o problema.

Você pode gerar uma lista de permutações N numerados n = 0 ... N-1 como

A_ij = (i * N + j + j * n * N) mod N^2

que gera uma nova permutação, deslocando as colunas em cada permutação. A linha superior da permutação de ordem n são as diagonais da permutação n-1Te. EDIT: Oops ... isso só parece funcionar quando N é primo.

Esta erra uma última permutação, que você pode obter ao transpor a matriz:

A_ij = j * N + i