Algoritmo para retornar todas as combinações de elementos de k a partir de n
https://stackoverflow.com/questions/127704
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu quero escrever uma função que recebe uma matriz de letras como um argumento e um número dessas cartas para selecionar.
Diga que proporcionar um leque de 8 letras e deseja selecionar 3 letras do que isso. Então você deve começar:
8! / ((8 - 3)! * 3!) = 56
Arrays (ou palavras), em troca, composto por 3 cartas cada um.
Solução
Art of Computer Programming Volume 4: Fascicle 3 tem uma tonelada destes que possa caber sua situação particular melhor do que como eu descrevo.
Códigos Grey
Uma questão que você vai encontrar é de memória curso e muito rapidamente, você vai ter problemas por 20 elementos no seu conjunto - 20 C 3 = 1140 . E se você quiser fazer uma iteração sobre o conjunto é melhor usar um algoritmo de código cinza modificada para que você não está segurando todas elas na memória. Estes gerar a seguinte combinação dos anteriores e evitar repetições. Existem muitos destes para diferentes usos. Queremos maximizar as diferenças entre combinações sucessivas? minimizar? et cetera.
Alguns dos artigos originais que descrevem os códigos de cinza:
- Alguns Hamilton Caminhos e um algoritmo alterar Minimal
- Adjacente Combinação Interchange Generation Algorithm
Aqui estão alguns outros documentos que cobrem o tópico:
- uma implementação eficiente dos Eades, Hickey, Leia Interchange Adjacente combinação Generation Algorithm (PDF, com código Pascal)
- Geradores de combinação
- Survey of Combinatória códigos Grey (PostScript)
- um algoritmo para códigos Grey
Chase giro (algoritmo)
Phillip J Chase, ` Algoritmo 382: Combinações de M fora de N Objectos '(1970)
O algoritmo em C ...
Índice de Combinações em lexicográfica Order (Buckles Algorithm 515)
É também possível fazer referência a uma combinação de pelo seu índice (em ordem léxicografica). Percebendo que o índice deve haver alguma quantidade de mudança da direita para a esquerda com base no índice podemos construir algo que deve recuperar uma combinação.
Assim, temos um conjunto {1,2,3,4,5,6} ... e queremos três elementos. Vamos dizer {1,2,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 é lexicographically número 2. Assim, o número de 'mudanças' no último lugar é responsável por um mudança na ordenação lexicográfica. O segundo lugar, com uma mudança {1,3,4} tem uma mudança, mas as contas para mais mudanças, uma vez que está em segundo lugar (proporcional ao número de elementos no conjunto original).
O método que eu descrevi é uma desconstrução, como parece, de conjunto com o índice, o que precisamos fazer o inverso - que é muito mais complicado. Isto é como Buckles resolve o problema. Eu escrevi alguns C para calcular los , com pequenas alterações - Eu usei o índice dos conjuntos em vez de um intervalo de números para representar o conjunto, por isso estamos sempre trabalhando a partir de 0 ... n. Nota:
- Uma vez que as combinações são desordenadas, {1,3,2} = {1,2,3} --nós encomendá-los para ser lexicográfico.
- Este método tem um implícito 0 para iniciar o jogo pela primeira diferença.
Índice de Combinações em lexicográfica Order (McCaffrey)
Não é outra maneira :, seu conceito é mais fácil de entender e programa, mas é, sem as otimizações de Buckles. Felizmente, também não produz combinações duplicados:
O conjunto 
que maximiza 
, onde 
.
Por exemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Assim, a combinação lexicographical 27 de quatro coisas é: {1,2,5,6}, esses são os índices de qualquer conjunto que você quer olhar. Exemplo abaixo (OCaml), requer função choose, da esquerda para a 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)
A combinações de pequenas e simples iterador
Os dois algoritmos seguintes são fornecidos para fins didáticos. Eles implementar um iterador e (a mais gerais) combinações pasta gerais.
Elas são tão rápido quanto possível, tendo a complexidade S ( n C k ). O consumo de memória é ligado por k.
Vamos começar com o iterador, que irá chamar uma função do usuário fornecido 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 vai chamar a função de utilizador fornecido juntamente com a variável de estado, a partir do estado inicial. Uma vez que precisamos para passar o estado entre estados diferentes não vamos usar o loop for-mas em vez disso, o uso de recursão,
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
Outras dicas
Em C #:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
Uso:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
Resultado:
123
124
125
134
135
145
234
235
245
345
solução java curto:
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
resultado será
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
Posso apresentar a minha solução Python recursiva para este problema?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
Exemplo de utilização:
>>> len(list(choose_iter("abcdefgh",3)))
56
Eu gosto dele por sua simplicidade.
Vamos dizer que o seu conjunto de letras esta aparência: "ABCDEFGH". Você tem três índices (i, j, k), indicando que as letras que você vai usar para a palavra atual, Você começa com:
A B C D E F G H ^ ^ ^ i j k
Primeiro você variar k, então o próximo passo olhares como esse:
A B C D E F G H ^ ^ ^ i j k
Se você chegou ao fim você vai em e variam j e k novamente.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Uma vez que j atingiram G você começa também a variar i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
escrito em código este olhar algo parecido
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]);
}
}
}
O seguinte algoritmo recursivo pega todas as combinações de k-elemento de um conjunto ordenado:
- escolha o primeiro elemento
ide sua combinação - combinar
icom cada uma das combinações de elementosk-1escolhidos de forma recursiva a partir do conjunto de elementos maiores do quei.
Iterate acima para cada i no conjunto.
É essencial que você escolher o resto dos elementos como maior do que i, à repetição evitar. Desta forma [3,5] será escolhido apenas uma vez, tal como [3] combinada com [5], em vez de duas vezes (os elimina estado [5] + [3]). Sem esta condição que você obter variações em vez de combinações.
Eu encontrei esta discussão útil e pensei que eu iria adicionar uma solução Javascript que você pode pop em Firebug. Dependendo do seu motor de JS, que pode demorar um pouco de tempo se a cadeia inicial é grande.
function string_recurse(active, rest) {
if (rest.length == 0) {
console.log(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
string_recurse(active, rest.substring(1, rest.length));
}
}
string_recurse("", "abc");
A saída deve ser a seguinte:
abc
ab
ac
a
bc
b
c
Em C ++ da seguinte rotina vai produzir todas as combinações de comprimento distância (em primeiro lugar, k) entre a gama [primeira, a última):
#include <algorithm>
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
Ele pode ser usado como este:
#include <string>
#include <iostream>
int main()
{
std::string s = "12345";
std::size_t comb_size = 3;
do
{
std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));
return 0;
}
Isto irá imprimir o seguinte:
123
124
125
134
135
145
234
235
245
345
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;
}
}
exemplo curta em Python:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
Para a explicação, o método recursiva é descrito com o seguinte exemplo:
Exemplo: A B C D E
Todas as combinações de 3 seria:
- A com todas as combinações de 2 a partir do resto (B C D E)
- B com todas as combinações de 2 a partir do resto (C D)
- C com todas as combinações de 2 a partir do resto (D E)
algoritmo recursivo simples em Haskell
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
Nós primeiro definir o caso especial, ou seja, selecionando zero elementos. Ela produz um único resultado, que é uma lista vazia (isto é, uma lista que contém uma lista vazia).
Para n> 0, x passa por cada elemento da lista e xs é cada elemento após x.
rest pega elementos n - 1 de xs usando uma chamada recursiva para combinations. O resultado final da função é uma lista, em que cada elemento é x : rest (isto é, uma lista que tem como x cabeça e rest como cauda) para cada valor diferente de x e rest.
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
E, claro, uma vez que Haskell é preguiçoso, a lista está gradualmente gerado, conforme necessário, para que possa avaliar parcialmente exponencialmente grandes combinações.
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
E aqui vem COBOL avô, a língua muito difamado.
Vamos assumir uma matriz de 34 elementos de oito bytes cada (selecção puramente arbitrária.) A ideia é a enumerar todas as possíveis combinações de 4-elemento e carregá-los em uma matriz.
Nós usamos 4 índices, um de cada para cada posição no grupo de 4
A matriz é processado como esta:
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
Nós variar idx4 de 4 até o fim. Para cada idx4 temos uma combinação única de grupos de quatro. Quando idx4 vem para o final da matriz, que idx3 incremento por um conjunto e idx4 para idx3 + 1. Então corremos idx4 até o fim novamente. Nós proceder desta maneira, aumentar idx3, idx2, e idx1 respectivamente até que a posição de idx1 é inferior a 4 a partir da extremidade da matriz. Que termina o algoritmo.
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
As primeiras iterações:
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
A COBOL exemplo:
01 DATA_ARAY.
05 FILLER PIC X(8) VALUE "VALUE_01".
05 FILLER PIC X(8) VALUE "VALUE_02".
etc.
01 ARAY_DATA OCCURS 34.
05 ARAY_ITEM PIC X(8).
01 OUTPUT_ARAY OCCURS 50000 PIC X(32).
01 MAX_NUM PIC 99 COMP VALUE 34.
01 INDEXXES COMP.
05 IDX1 PIC 99.
05 IDX2 PIC 99.
05 IDX3 PIC 99.
05 IDX4 PIC 99.
05 OUT_IDX PIC 9(9).
01 WHERE_TO_STOP_SEARCH PIC 99 COMP.
* Stop the search when IDX1 is on the third last array element:
COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3
MOVE 1 TO IDX1
PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
COMPUTE IDX2 = IDX1 + 1
PERFORM UNTIL IDX2 > MAX_NUM
COMPUTE IDX3 = IDX2 + 1
PERFORM UNTIL IDX3 > MAX_NUM
COMPUTE IDX4 = IDX3 + 1
PERFORM UNTIL IDX4 > MAX_NUM
ADD 1 TO OUT_IDX
STRING ARAY_ITEM(IDX1)
ARAY_ITEM(IDX2)
ARAY_ITEM(IDX3)
ARAY_ITEM(IDX4)
INTO OUTPUT_ARAY(OUT_IDX)
ADD 1 TO IDX4
END-PERFORM
ADD 1 TO IDX3
END-PERFORM
ADD 1 TO IDX2
END_PERFORM
ADD 1 TO IDX1
END-PERFORM.
Aqui é um elegante, implementação genérica no Scala, como descrito em 99 Scala Problemas .
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}
Se você pode usar sintaxe SQL - por exemplo, se você estiver usando LINQ para acessar campos de uma estrutura ou matriz, ou diretamente acessando um banco de dados que tem uma tabela chamada "Alphabet" com apenas um campo char "Letter", você pode adaptar seguinte código:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
Isso irá retornar todas as combinações de 3 letras, não obstante quantas cartas você tem na tabela "Alphabet" (que pode ser de 3, 8, 10, 27, etc.).
Se o que você quer é todas as permutações, ao invés de combinações (ou seja, você quer "ACB" e "ABC" para contar como diferente, em vez de aparecer apenas uma vez) simplesmente apagar a última linha (o E um) e ele é feito.
Post-Edit: Depois de re-ler a pergunta, eu percebo o que é necessário é a Geral algoritmo, e não apenas um específico para o caso de selecionar 3 itens. resposta Adam Hughes é o completo, infelizmente, não posso votar-lo (ainda). simples deste resposta, mas funciona somente para quando você quer exatamente 3 itens.
Outra versão C # com a geração preguiçosa dos índices de combinação. Esta versão mantém um único conjunto de índices para definir um mapeamento entre a lista de todos os valores e os valores para a combinação de corrente, ou seja, usa constantemente O (k) espaço adicional durante todo o tempo de execução. O código gera combinações individuais, incluindo o primeiro, em O (k) tempo.
public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
if (k < 0 || values.Length < k)
yield break; // invalid parameters, no combinations possible
// generate the initial combination indices
var combIndices = new int[k];
for (var i = 0; i < k; i++)
{
combIndices[i] = i;
}
while (true)
{
// return next combination
var combination = new T[k];
for (var i = 0; i < k; i++)
{
combination[i] = values[combIndices[i]];
}
yield return combination;
// find first index to update
var indexToUpdate = k - 1;
while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
{
indexToUpdate--;
}
if (indexToUpdate < 0)
yield break; // done
// update combination indices
for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
{
combIndices[indexToUpdate] = combIndex;
}
}
}
código de teste:
foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
System.Console.WriteLine(String.Join(" ", combination));
}
Output:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
Aqui você tem uma versão preguiçoso avaliadas desse algoritmo codificado em C #:
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
E test parte:
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
Espero que isso ajude!
Eu tinha um algoritmo de permutação I utilizado para Euler projeto, em python:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
Se
n<len(l)
você deve ter todas as combinações que você precisa sem repetição, você precisa dele?
É um gerador, para que você usá-lo em algo como isto:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
https://gist.github.com/3118596
Há uma implementação para JavaScript. Tem funções para obter k-combinações e todas as combinações de uma série de quaisquer objectos. Exemplos:
k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]
combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
Versão Clojure:
(defn comb [k l]
(if (= 1 k) (map vector l)
(apply concat
(map-indexed
#(map (fn [x] (conj x %2))
(comb (dec k) (drop (inc %1) l)))
l))))
Vamos dizer que o seu conjunto de letras esta aparência: "ABCDEFGH". Você tem três índices (i, j, k), indicando que as letras que você vai usar para a palavra atual, Você começa com:
A B C D E F G H ^ ^ ^ i j k
Primeiro você variar k, então o próximo passo olhares como esse:
A B C D E F G H ^ ^ ^ i j k
Se você chegou ao fim você vai em e variam j e k novamente.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Uma vez que j atingiram G você começa também a variar i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
function initializePointers($cnt) {
$pointers = [];
for($i=0; $i<$cnt; $i++) {
$pointers[] = $i;
}
return $pointers;
}
function incrementPointers(&$pointers, &$arrLength) {
for($i=0; $i<count($pointers); $i++) {
$currentPointerIndex = count($pointers) - $i - 1;
$currentPointer = $pointers[$currentPointerIndex];
if($currentPointer < $arrLength - $i - 1) {
++$pointers[$currentPointerIndex];
for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
}
return true;
}
}
return false;
}
function getDataByPointers(&$arr, &$pointers) {
$data = [];
for($i=0; $i<count($pointers); $i++) {
$data[] = $arr[$pointers[$i]];
}
return $data;
}
function getCombinations($arr, $cnt)
{
$len = count($arr);
$result = [];
$pointers = initializePointers($cnt);
do {
$result[] = getDataByPointers($arr, $pointers);
} while(incrementPointers($pointers, count($arr)));
return $result;
}
$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);
Com base https://stackoverflow.com/a/127898/2628125 , mas mais abstrata, para qualquer tamanho de ponteiros.
Eu criei uma solução no SQL Server 2005 para isso, e postou no meu site: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
Aqui está um exemplo para uso show:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
resultados:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
Aqui é a minha proposição em C ++
Eu tentei impor o mínimo de restrição quanto ao tipo iterator como eu poderia por isso esta solução pressupõe apenas encaminhar iterador, e pode ser um const_iterator. Isso deve funcionar com qualquer recipiente padrão. Nos casos em que os argumentos não fazem sentido ele lança std :: invalid_argumnent
#include <vector>
#include <stdexcept>
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
Tudo dito e feito e aqui vem o código O'caml para isso. Algoritmo é evidente a partir do código ..
let combi n lst =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
[] -> []
| (h::t) -> (combi t (h::c))@(combi t c)
in
combi lst []
;;
Aqui está um código que eu escrevi recentemente em Java, que calcula e retorna toda a combinação de elementos "num" de elementos "outof".
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
Uma solução Javascript concisa:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
Aqui está um método que lhe dá todas as combinações de tamanho especificado a partir de uma cadeia de comprimento aleatório. Semelhantes a solução quinmars, mas obras para a entrada variada e k.
O código pode ser alterado para envolver em torno de, ou seja, 'salpico' de entrada 'abcd' w k = 3.
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
Saída para "ABCDE":
abc abd abe acd ace ade BCD bce bde cde
Eu escrevi uma classe para lidar com funções comuns para trabalhar com o coeficiente binomial, que é o tipo de problema que seu problema se enquadra. Ele executa as seguintes tarefas:
-
Saídas todos os K-índices em um formato agradável para qualquer N escolher K para um arquivo. Os K-índices pode ser substituído com cadeias mais descritivos ou letras. Este método faz com que a solução deste tipo de problema bastante trivial.
-
Converte o K-índices para o índice apropriado de uma entrada no classificadas tabela de coeficiente binomial. Esta técnica é muito mais rápido do que as técnicas publicadas mais velhos que dependem de iteração. Ele faz isso usando uma propriedade matemática inerente triângulo de Pascal. Meu trabalho fala sobre isso. Eu acredito que eu sou o primeiro a descobrir e publicar esta técnica, mas posso estar errado.
-
Converte o índice numa tabela classificados coeficiente binomial para os correspondentes K-índices.
-
Mark Dominus para calcular o coeficiente binomial, que é muito menos probabilidade de estouro e trabalha com números maiores.
-
A classe está escrito em .NET C # e fornece uma maneira de gerenciar os objetos relacionados com o problema (se houver) usando uma lista genérica. O construtor desta classe assume um valor booleano chamado InitTable que, quando verdadeiro irá criar uma lista genérica para segurar os objetos a serem gerenciados. Se este valor é falso, então ele não vai criar a tabela. A tabela não precisam ser criados, a fim de realizar a 4 acima métodos. Acessores métodos são fornecidos para acessar a tabela.
-
Há uma classe de teste associada que mostra como usar a classe e seus métodos. Ele foi testado extensivamente com 2 casos e não são erros não conhecido.
Para ler sobre esta classe e baixar o código, consulte Tablizing o binômio Coeffieicent .
Não deve ser difícil para converter essa classe para C ++.
Algoritmo:
- contar de 1 a 2 ^ n.
- Converter cada dígito a sua representação binária.
- Traduzir cada 'on' pouco para elementos do seu conjunto, com base na posição.
Em C #:
void Main()
{
var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
var kElement = 2;
for(var i = 1; i < Math.Pow(2, set.Length); i++) {
var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
var cnt = Regex.Matches(Regex.Escape(result), "1").Count;
if (cnt == kElement) {
for(int j = 0; j < set.Length; j++)
if ( Char.GetNumericValue(result[j]) == 1)
Console.Write(set[j]);
Console.WriteLine();
}
}
}
Porque é que funciona?
Há uma bijeç~ao entre os subconjuntos de um conjunto de n elementos e sequências de n-bit.
Isso significa que podemos descobrir quantos subconjuntos existem por seqüências de contagem.
por exemplo., O conjunto de quatro elemento inferior pode ser representado por {0,1} X {0, 1} X {0, 1} X {0, 1} (ou 2 ^ 4) sequências diferentes.
Assim - tudo o que temos a fazer é contar de 1 a 2 ^ n para encontrar todas as combinações seguida, traduzir os dígitos à sua representação binária. (Nós ignoramos o conjunto vazio.). elementos, em seguida, substitutos do seu conjunto para 'on' BITS.
Se você quiser apenas k resultados elementos, imprimir apenas quando k bits são 'on'.
(Se você quiser todos os subconjuntos em vez de subconjuntos comprimento K, remova a parte cnt / kElement.)
(Para a prova, ver MIT livre cursos Matemática para Ciência da Computação, Lehman et al, seção 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/ 6-042j-matemática-para-computer-science-queda-2010 / leituras / )
Entrando na onda, e postar outra solução. Esta é uma implementação Java genérico. Entrada: (int k) é o número de elementos a escolher e (List<T> list) a lista para escolher. Retorna uma lista de combinações (List<List<T>>).
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
