Quero escrever uma função que tome uma série de letras como argumento e um número dessas letras para seleccionar.
Digamos que você fornece um conjunto de 8 letras e quer selecionar 3 letras a partir disso. Então você deve conseguir:
8! / ((8 - 3)! * 3!) = 56
Arrays (ou palavras) em troca consistindo de 3 letras cada.
Um problema com o qual se deparará é, naturalmente, a memória e muito rapidamente, você'terá problemas por 20 elementos no seu conjunto -- 20C3 = 1140. E se você quiser iterar sobre o set it's melhor usar um algoritmo de código cinza modificado para que você esteja't mantendo todos eles na memória. Estes geram a próxima combinação a partir da anterior e evitam repetições. Existem muitos destes para diferentes usos. Queremos maximizar as diferenças entre as sucessivas combinações? minimizar? et cetera. Alguns dos trabalhos originais descrevem códigos cinzentos:
Você também pode fazer referência a uma combinação pelo seu índice (em ordem lexicográfica). Percebendo que o índice deve ser alguma quantidade de mudança da direita para a esquerda com base no índice podemos construir algo que deve recuperar uma combinação. Portanto, temos um conjunto {1,2,3,4,5,6}... e queremos três elementos. Digamos que {1,2,3,3} podemos dizer que a diferença entre os elementos é um e em ordem e mínima. {1,2,4} tem uma mudança e é lexicograficamente número 2. Então o número de 'muda' no último lugar é responsável por uma mudança na ordenação lexicográfica. O segundo lugar, com uma alteração {1,3,4} tem uma alteração mas é responsável por mais alterações desde's no segundo lugar (proporcional ao número de elementos do conjunto original). O método I've descrito é uma desconstrução, como parece, do set para o índice, precisamos fazer o inverso - o que é muito mais complicado. É assim que Fivelas resolve o problema. Eu escrevi alguns C para calculá-los, com pequenas alterações - eu usei o índice dos conjuntos ao invés de um intervalo de números para representar o conjunto, então estamos sempre trabalhando a partir de 0...n. Nota:
Há outra maneira:, seu conceito é mais fácil de entender e programar, mas ele's sem as otimizações de Fivelas. Felizmente, ele também não produz combinações duplicadas:
O conjunto que maximiza , onde .
Para um exemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. Assim, a 27ª combinação lexicográfica de quatro coisas é: {1,2,5,6}, esses são os índices de qualquer conjunto que se queira ver. Exemplo abaixo (OCaml), requer a função "escolha", deixada para o leitor:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
Os dois algoritmos seguintes são fornecidos para fins didácticos. Eles implementam um iterador e (uma pasta mais geral) combinações gerais. Eles são o mais rápido possível, tendo a complexidade O(nCk). O consumo de memória é limitado por `k'. Vamos começar com o iterador, que chamará uma função fornecida pelo usuário para cada combinação
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
Uma versão mais geral chamará a função fornecida pelo usuário junto com a variável de estado, começando a partir do estado inicial. Como precisamos passar o estado entre estados diferentes, nós ganhamos'não usamos o for-loop, mas em vez disso, usamos a recursividade,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
Digamos que seu conjunto de cartas se parece com isto: "ABCDEFGH". Você tem três índices (i, j, k) indicando quais letras você vai usar para a palavra atual, Você começa com:
A B C C D E F G H ^ ^ ^ i j k Primeiro você varia k, então o próximo passo parece ser esse:A B C C D E F G H ^ ^ ^ i j k Se você chegar ao fim, você continua e varia j e depois k novamente.A B C C D E F G H ^ ^ ^ i j kA B C C D E F G H ^ ^ ^ i j k </pregt;
Uma vez que você chegou a G você também começa a variar i.
A B C C D E F G H ^ ^ ^ i j kA B C C D E F G H ^ ^ ^ i j k ... ... </pregt;
Escrito em código, isto parece algo assim
void print_combinations(const char *string) { int i, j, k; int len = strlen(string); for (i = 0; i < len - 2; i++) { for (j = i + 1; j < len - 1; j++) { for (k = j + 1; k < len; k++) printf("%c%c%c\n", string[i], string[j], string[k]); } } }
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}