Como calcular permutações no tempo linear, com uma reviravolta
https://stackoverflow.com/questions/483890
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho um problema de agendamento de recursos em Java, onde as coisas precisam ser sequenciadas, mas há restrições sobre quais recursos podem estar próximos um do outro. Uma boa analogia é uma sequência de "dígitos", onde apenas certos dígitos podem estar próximos um do outro. Minha solução foi recursiva e funciona bem para pequenas cordas, mas o tempo de execução é O (x^n), onde x é o número de dígitos possíveis (a base) e n é o comprimento da corda. Rapidamente se torna incontrolável.
Usando a matriz de compatibilidade abaixo, aqui estão alguns exemplos de strings permitidos
Comprimento de 1: 0, 1, 2, 3, 4
Comprimento de 2: 02, 03, 14, 20, 30, 41
Comprimento de 3: 020, 030, 141, 202, 203, 302, 303, 414
0 1 2 3 4 --------------------- 0| 0 0 1 1 0 1| 0 0 0 0 1 2| 1 0 0 0 0 3| 1 0 0 0 0 4| 0 1 0 0 0
Minha solução para contar todas as seqüências de comprimento n foi iniciada com uma corda vazia, permite o primeiro dígito e fazer uma chamada recursiva para todas as seqüências de comprimento N-1. As chamadas recursivas verificam o último dígito que foi adicionado e tente todas as permutações que podem estar próximas desse dígito. Existem algumas otimizações feitas para que eu não tente e permita 00, 01, 04 sempre, por exemplo - apenas 02, 03, mas o desempenho ainda é ruim, pois é escalado da base 5 (o exemplo) para a base 4000.
Alguma opinião sobre uma maneira melhor de contar as permutações além de tentar enumerar todas elas?
Solução
Se você deseja apenas o número de cordas de um certo comprimento, você pode multiplicar a matriz de compatibilidade por si mesma algumas vezes e soma seus valores.
n = comprimento da corda
UMA = Matriz de compatibilidade
Número de cordas possíveis = soma de UMAn-1
Alguns exemplos:
n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5
n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8
n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34
A matriz original (linha eu, coluna j) poderia ser pensado como o número de cordas que começam com símbolo eu, e cujo próximo símbolo é o símbolo j. Como alternativa, você pode vê -lo como número de seqüências de comprimento 2, que começa com símbolo eu e termina com símbolo j.
A multiplicação da matriz preserva esse invariante, então após a exponenciação, UMAn-1 conteria o número de cordas que começam com símbolo eu, tem comprimento n, e termina em símbolo j.
Ver Wikipedia: Exponention by Squaring Para um algoritmo para um cálculo mais rápido dos poderes da matriz.
(Obrigado Stefan.ciobaca)
Este caso específico reduz à fórmula:
Número de cordas possíveis = f(n) = 4 + Σk=1..n 2⌊k-1⁄2⌋ = f(n-1) + 2⌊n-1⁄2⌋
n f(n)
---- ----
1 5
2 6
3 8
4 10
5 14
6 18
7 26
8 34
9 50
10 66
Outras dicas
Você só quer saber quantas cordas de um determinado comprimento você pode construir com as regras da matriz especificada? Nesse caso, uma abordagem como essa deve funcionar:
n = 5
maxlen = 100
combine = [
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0]
]
# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]
for size in range(2, maxlen+1):
# calculate counts for size from count for (size-1)
newcount = []
for next in range(n):
total = 0
for head in range(n):
if combine[next][head]:
# |next| can be before |head|, so add the counts for |head|
total += counts[head]
# append, so that newcount[next] == total
newcount.append(total)
counts = newcount
print "length %i: %i items" % (size, sum(counts))
Seu algoritmo parece ser ideal.
Como você está usando essas permutações? Você os está acumulando em uma lista ou usando uma por uma? Como há um grande número dessas permutações, o desempenho ruim talvez devido ao uso de memória grande (se você estiver coletando todas elas) ou leva muito tempo. Você simplesmente não pode fazer bilhões de loops em tempo trivial.
Responder a comentar:
Se você deseja apenas contá -los, pode usar a programação dinâmica:
Vamos contar [n] [m] ser uma matriz, onde o conde [l] [j] é o número de tais permutações cujo comprimento é l e termina com j,
então conte [l] [i] = contagem [l-1] [i1]+count [l-1] [i2]+..., onde i1, i2, ... são os dígitos que podem preceder i (isso pode ser salvo em uma matriz pré-calculada).
Toda célula da contagem pode ser preenchida somando os números K (k depende da matriz compatível), portanto a complexidade é O (kmn), m é o comprimento da permutação e n é o número total de dígitos.
Talvez eu não entenda isso, mas isso não seria servido com uma tabela de listas que, para cada dígito, possui uma lista de dígitos válidos que poderiam segui -lo.
Em seguida, sua rotina para gerar receberá um resultado acumulado, o número do dígito e o dígito atual. Algo como:
// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
if (currIndex == kMaxIndex) {
NotifyComplete(result);
return;
}
char[] validFollows = GetValidFollows(currDigit); // table lookup
foreach (char c in validFollows) {
result[currIndex] = c;
GenerateDigits(result, currIndex+1, c);
}
}
A complexidade aumenta em função do número de dígitos a serem gerados, mas essa função depende do número total de seguidores válidos para qualquer um dígito. Se o número total de seguidores for o mesmo para cada dígito, digamos, k, então o tempo para gerar todas as permutações possíveis será o (k^n), onde n é o número de dígitos. Desculpe, não posso mudar de matemática. O tempo para gerar n dígitos na base 10 é 10^n.
Não sei exatamente o que você está perguntando, mas como existem potencialmente n! Permutações de uma sequência de n dígitos, você não poderá listá -los mais rapidamente que N!. Não sei exatamente como você acha que tem um tempo de execução de O (n^2).
