Algoritmo per restituire tutte le combinazioni di k elementi da n
https://stackoverflow.com/questions/127704
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Voglio scrivere una funzione che accetta una matrice di lettere come argomento e un numero di quelle lettere da selezionare.
Supponi di fornire una matrice di 8 lettere e che desideri selezionare 3 lettere da quella. Quindi dovresti ottenere:
8! / ((8 - 3)! * 3!) = 56
Matrici (o parole) in cambio composte da 3 lettere ciascuna.
Soluzione
Art of Computer Programming Volume 4: Fascicle 3 ha un sacco di questi che potrebbero adattarsi alla tua situazione particolare meglio di come descrivo.
Codici grigi
Un problema che incontrerai è ovviamente la memoria e abbastanza rapidamente, avrai problemi di 20 elementi nel tuo set - 20 C 3 = 1140 E se vuoi iterare sul set, è meglio usare un algoritmo di codice grigio modificato in modo da non tenerli tutti in memoria. Questi generano la combinazione successiva dalla precedente ed evitano le ripetizioni. Ce ne sono molti per usi diversi. Vogliamo massimizzare le differenze tra combinazioni successive? minimizzare? eccetera.
Alcuni dei documenti originali che descrivono i codici grigi:
- Alcuni percorsi di Hamilton e un algoritmo di modifica minima
- Algoritmo di generazione della combinazione di interscambio adiacente
Ecco alcuni altri articoli che trattano l'argomento:
- Un'attuazione efficiente di Eades, Hickey, Read Adiacente interscambio Combination Generation Algorithm (PDF, con codice in Pascal)
- Generatori di combinazioni
- Sondaggio sui codici grigi combinatori (PostScript)
- Un algoritmo per codici grigi
Chase's Twiddle (algoritmo)
Phillip J Chase, ` Algoritmo 382: Combinazioni di M su N oggetti '(1970)
L'algoritmo in C ...
Indice delle combinazioni nell'ordine lessicografico (Buckles Algorithm 515)
Puoi anche fare riferimento a una combinazione in base al suo indice (in ordine lessicografico). Comprendendo che l'indice dovrebbe essere una certa quantità di cambiamento da destra a sinistra in base all'indice, possiamo costruire qualcosa che dovrebbe recuperare una combinazione.
Quindi, abbiamo un set {1,2,3,4,5,6} ... e vogliamo tre elementi. Diciamo {1,2,3} possiamo dire che la differenza tra gli elementi è una e in ordine e minima. {1,2,4} ha una modifica ed è lessicograficamente il numero 2. Quindi il numero di "modifiche" all'ultimo posto rappresenta una variazione nell'ordinamento lessicografico. Il secondo posto, con una modifica {1,3,4} ha una modifica, ma tiene conto di altre modifiche poiché è al secondo posto (proporzionale al numero di elementi nel set originale).
Il metodo che ho descritto è una decostruzione, come sembra, dall'impostazione all'indice, dobbiamo fare il contrario & # 8211; che è molto più complicato. Ecco come Buckles risolve il problema. Ho scritto alcuni C per calcolarli , con lievi modifiche < !> # 8211; Ho usato l'indice degli insiemi piuttosto che un intervallo di numeri per rappresentare l'insieme, quindi lavoriamo sempre da 0 ... n. Nota:
- Poiché le combinazioni non sono ordinate, {1,3,2} = {1,2,3} - ordiniamo che siano lessicografiche.
- Questo metodo ha uno 0 implicito per avviare il set per la prima differenza.
Indice delle combinazioni in Lexicographical Order (McCaffrey)
C'è un altro modo : il suo concetto è più facile da capire e programmare, ma è senza le ottimizzazioni di Buckles. Fortunatamente, non produce anche combinazioni duplicate:
Il set 
che massimizza 
, dove 
.
Per un esempio: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Quindi, la 27a combinazione lessicografica di quattro cose è: {1,2,5,6}, questi sono gli indici di qualunque set tu voglia guardare. Esempio sotto (OCaml), richiede choose funzione, lasciato al lettore:
(* 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)
Un iteratore di combinazioni piccole e semplici
I seguenti due algoritmi sono forniti a scopo didattico. Implementano combinazioni iteratrici e (più generali) di cartelle.
Sono il più veloci possibile, con la complessità O ( n C k ). Il consumo di memoria è limitato da k.
Inizieremo con l'iteratore, che chiamerà una funzione fornita dall'utente per ogni combinazione
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
Una versione più generale chiamerà la funzione fornita dall'utente insieme alla variabile di stato, a partire dallo stato iniziale. Dato che dobbiamo passare lo stato tra stati diversi, non useremo il for-loop, ma utilizzeremo invece la ricorsione,
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
Altri suggerimenti
In 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)));
}
Utilizzo:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
Risultato:
123
124
125
134
135
145
234
235
245
345
Soluzione java breve:
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);
}
}
}
Il risultato sarà
[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 presentare la mia soluzione Python ricorsiva a questo 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))
Esempio di utilizzo:
>>> len(list(choose_iter("abcdefgh",3)))
56
Mi piace per la sua semplicità.
Diciamo che il tuo array di lettere è simile al seguente: " ABCDEFGH " ;. Hai tre indici (i, j, k) che indicano quali lettere utilizzerai per la parola corrente. Inizia con:
A B C D E F G H ^ ^ ^ i j k
Prima devi variare k, quindi il passaggio successivo è simile al seguente:
A B C D E F G H ^ ^ ^ i j k
Se hai raggiunto la fine vai avanti e vari j e poi di nuovo k.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Una volta che hai raggiunto G, inizi anche a variare i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
Scritto nel codice questo sembra qualcosa del genere
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]);
}
}
}
Il seguente algoritmo ricorsivo seleziona tutte le combinazioni di elementi k da un set ordinato:
- scegli il primo elemento
idella tua combinazione - combina
k-1con ciascuna delle combinazioni di <=> elementi scelti ricorsivamente dall'insieme di elementi più grandi di <=>.
Iterate quanto sopra per ogni <=> nel set.
È essenziale scegliere il resto degli elementi più grande di <=>, per evitare la ripetizione. In questo modo [3,5] verrà scelto una sola volta, come [3] combinato con [5], anziché due volte (la condizione elimina [5] + [3]). Senza questa condizione si ottengono variazioni anziché combinazioni.
Ho trovato utile questa discussione e ho pensato di aggiungere una soluzione Javascript che puoi inserire in Firebug. A seconda del tuo motore JS, potrebbe essere necessario un po 'di tempo se la stringa iniziale è 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");
L'output dovrebbe essere il seguente:
abc
ab
ac
a
bc
b
c
In C ++ la seguente routine produrrà tutte le combinazioni di distanza (first, k) tra la gamma [first, last):
#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;
}
Può essere usato in questo modo:
#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;
}
Questo stamperà quanto segue:
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;
}
}
Breve esempio in 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
Per una spiegazione, il metodo ricorsivo è descritto con il seguente esempio:
Esempio: A B C D E
Tutte le combinazioni di 3 sarebbero:
- A con tutte le combinazioni di 2 dal resto (B C D E)
- B con tutte le combinazioni di 2 dal resto (C D E)
- C con tutte le combinazioni di 2 dal resto (D E)
Semplice algoritmo ricorsivo in Haskell
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
Definiamo innanzitutto il caso speciale, ovvero selezionando zero elementi. Produce un singolo risultato, che è un elenco vuoto (ovvero un elenco che contiene un elenco vuoto).
Per n > 0, x attraversa tutti gli elementi dell'elenco e xs è ogni elemento dopo rest.
n - 1 seleziona combinations elementi da x : rest utilizzando una chiamata ricorsiva a <=>. Il risultato finale della funzione è un elenco in cui ogni elemento è <=> (ovvero un elenco che ha <=> come capo e <=> come coda) per ogni diverso valore di <=> e <=>.
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
E ovviamente, dato che Haskell è pigro, l'elenco viene gradualmente generato in base alle esigenze, in modo da poter valutare parzialmente combinazioni esponenzialmente grandi.
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
Ed ecco che arriva il nonno COBOL, il linguaggio molto diffamato.
Supponiamo che un array di 34 elementi di 8 byte ciascuno (selezione puramente arbitraria.) L'idea è quella di enumerare tutte le possibili combinazioni di 4 elementi e caricarle in un array.
Utilizziamo 4 indici, uno per ciascuna posizione nel gruppo di 4
L'array viene elaborato in questo modo:
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
Variamo idx4 da 4 alla fine. Per ogni idx4 otteniamo una combinazione unica di gruppi di quattro. Quando idx4 arriva alla fine dell'array, incrementiamo idx3 di 1 e impostiamo idx4 su idx3 + 1. Quindi eseguiamo di nuovo idx4 fino alla fine. Procediamo in questo modo, aumentando rispettivamente idx3, idx2 e idx1 fino a quando la posizione di idx1 è inferiore a 4 dalla fine dell'array. Questo completa l'algoritmo.
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
Prime iterazioni:
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
Un esempio di COBOL:
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.
Ecco un'implementazione generica ed elegante in Scala, come descritto in 99 Scala Problems .
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 è possibile utilizzare la sintassi SQL, ad esempio se si utilizza LINQ per accedere ai campi di una struttura o di un array o si accede direttamente a un database con una tabella denominata " Alphabet " con un solo campo char " Letter " puoi adattare il seguente codice:
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
Questo restituirà tutte le combinazioni di 3 lettere, nonostante quante lettere hai nella tabella " Alphabet " (può essere 3, 8, 10, 27, ecc.).
Se quello che vuoi sono tutte le permutazioni, piuttosto che le combinazioni (cioè vuoi " ACB " e " ABC " contare come diversi, piuttosto che apparire solo una volta) basta eliminare l'ultima riga (quella AND) ed è fatta.
Post-Edit: dopo aver riletto la domanda, mi rendo conto che è necessario l'algoritmo generale , non solo uno specifico per la selezione di 3 elementi. La risposta di Adam Hughes è completa, purtroppo non posso ancora votarla. Questa risposta è semplice ma funziona solo quando vuoi esattamente 3 elementi.
Un'altra versione C # con generazione pigra degli indici di combinazione. Questa versione mantiene un unico array di indici per definire una mappatura tra l'elenco di tutti i valori e i valori per la combinazione corrente, ovvero utilizza costantemente O (k) spazio aggiuntivo durante l'intero runtime. Il codice genera combinazioni individuali, inclusa la prima, in O (k) volta.
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;
}
}
}
Codice test:
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
Qui hai una versione lazy valutata di quell'algoritmo codificato in 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 parte di prova:
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));
}
}
Spero che questo ti aiuti!
Avevo un algoritmo di permutazione che ho usato per il progetto euler, in 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)
dovresti avere tutte le combinazioni di cui hai bisogno senza ripetizioni, ne hai bisogno?
È un generatore, quindi lo usi in qualcosa del genere:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
https://gist.github.com/3118596
Esiste un'implementazione per JavaScript. Ha funzioni per ottenere combinazioni k e tutte le combinazioni di una matrice di qualsiasi oggetto. Esempi:
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;
}
Versione 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))))
Diciamo che il tuo array di lettere è simile al seguente: & Quot; ABCDEFGH & Quot ;. Hai tre indici (i, j, k) che indicano quali lettere utilizzerai per la parola corrente. Inizia con:
A B C D E F G H ^ ^ ^ i j k
Prima devi variare k, quindi il passaggio successivo è simile al seguente:
A B C D E F G H ^ ^ ^ i j k
Se hai raggiunto la fine vai avanti e vari j e poi di nuovo k.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Una volta che hai raggiunto G, inizi anche a variare 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);
Basato su https://stackoverflow.com/a/127898/2628125 , ma più astratto, per qualsiasi dimensione di puntatori.
Ho creato una soluzione in SQL Server 2005 per questo e l'ho pubblicata sul mio sito Web: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
Ecco un esempio per mostrare l'utilizzo:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
Risultati:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
Ecco la mia proposta in C ++
Ho cercato di imporre il minor numero di iteratori sul limite possibile, quindi questa soluzione presuppone solo un iteratore in avanti e può essere un const_iterator. Questo dovrebbe funzionare con qualsiasi contenitore standard. Nei casi in cui gli argomenti non hanno senso, genera 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));
}
}
Detto questo, ecco il codice O'caml. L'algoritmo è evidente dal codice ..
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 []
;;
Ecco un codice che ho scritto di recente in Java, che calcola e restituisce tutta la combinazione di & Quot; num & Quot; elementi da " outOf " elementi.
// 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);
}
}
Una soluzione 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);
Ecco un metodo che ti dà tutte le combinazioni di dimensioni specificate da una stringa di lunghezza casuale. Simile alla soluzione di Quinmars, ma funziona con input e k vari
Il codice può essere modificato per essere completato, ovvero "dab" dall'input "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);
}
}
Output per " abcde " ;:
abc abd abe acd ace ade bcd bce bde cde
Ho scritto una classe per gestire le funzioni comuni per lavorare con il coefficiente binomiale, che è il tipo di problema che rientra nel problema. Svolge le seguenti attività:
-
Stampa tutti gli indici K in un bel formato per qualsiasi N, scegli K in un file. Gli indici K possono essere sostituiti con stringhe o lettere più descrittive. Questo metodo rende banale la risoluzione di questo tipo di problema.
-
Converte gli indici K nell'indice corretto di una voce nella tabella dei coefficienti binomiali ordinati. Questa tecnica è molto più veloce delle vecchie tecniche pubblicate che si basano sull'iterazione. Lo fa usando una proprietà matematica inerente al Triangolo di Pascal. Il mio articolo parla di questo. Credo di essere il primo a scoprire e pubblicare questa tecnica, ma potrei sbagliarmi.
-
Converte l'indice in una tabella di coefficienti binomiali ordinata nei corrispondenti indici K.
-
Utilizza il metodo Mark Dominus per calcolare il coefficiente binomiale, che è molto ha meno probabilità di traboccare e funziona con numeri maggiori.
-
La classe è scritta in .NET C # e fornisce un modo per gestire gli oggetti relativi al problema (se presenti) usando un elenco generico. Il costruttore di questa classe prende un valore booleare chiamato InitTable che quando true creerà un elenco generico per contenere gli oggetti da gestire. Se questo valore è falso, non creerà la tabella. Non è necessario creare la tabella per eseguire i 4 metodi precedenti. Sono disponibili metodi di accesso per accedere alla tabella.
-
Esiste una classe di test associata che mostra come utilizzare la classe e i suoi metodi. È stato ampiamente testato con 2 casi e non ci sono bug noti.
Per leggere questa lezione e scaricare il codice, vedere Tablizing The Binomial Coeffieicent .
Non dovrebbe essere difficile convertire questa classe in C ++.
Algoritmo:
- Contare da 1 a 2 ^ n.
- Converti ogni cifra nella sua rappresentazione binaria.
- Traduci ogni bit 'on' in elementi del tuo set, in base alla posizione.
In 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();
}
}
}
Perché funziona?
Esiste una biiezione tra i sottoinsiemi di un set di elementi n e sequenze n-bit.
Ciò significa che possiamo capire quanti sottoinsiemi esistono contando le sequenze.
ad esempio, i quattro elementi impostati di seguito possono essere rappresentati da {0,1} X {0, 1} X {0, 1} X {0, 1} (o 2 ^ 4) sequenze diverse.
Quindi - tutto ciò che dobbiamo fare è contare da 1 a 2 ^ n per trovare tutte le combinazioni. (Ignoriamo il set vuoto.) Successivamente, traduci le cifre nella loro rappresentazione binaria. Quindi sostituisci gli elementi del tuo set con bit "on".
Se vuoi solo i risultati dell'elemento k, stampa solo quando k bit sono 'on'.
(Se si desidera tutti i sottoinsiemi anziché i sottoinsiemi k length, rimuovere la parte cnt / kElement.)
(Per la prova, consultare il corso gratuito MIT Mathematics for Computer Science, Lehman et al, sezione 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/ 6-042j-matematica-per-informatica-scienza-autunno-2010 / letture / )
Saltare sul carro e pubblicare un'altra soluzione. Questa è un'implementazione Java generica. Input: (int k) è il numero di elementi da scegliere e (List<T> list) è l'elenco da scegliere. Restituisce un elenco di combinazioni (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;
}
