algorithm - todas - permutaciones
Algoritmo para devolver todas las combinaciones de k elementos de n (30)
¿Puedo presentar mi solución de Python recursiva a 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))
Ejemplo de uso:
>>> len(list(choose_iter("abcdefgh",3)))
56
Me gusta por su sencillez.
Quiero escribir una función que tome una matriz de letras como un argumento y un número de esas letras para seleccionar.
Supongamos que proporciona una matriz de 8 letras y desea seleccionar 3 letras de esa. Entonces deberías obtener:
8! / ((8 - 3)! * 3!) = 56
Arreglos (o palabras) a cambio consisten de 3 letras cada uno.
Algoritmo recursivo simple en Haskell
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
Primero definimos el caso especial, es decir, seleccionando cero elementos. Produce un solo resultado, que es una lista vacía (es decir, una lista que contiene una lista vacía).
Para n> 0, x recorre todos los elementos de la lista y xs es cada elemento después de x .
rest escoge n - 1 elementos de xs usando una llamada recursiva a combinations . El resultado final de la función es una lista donde cada elemento es x : rest (es decir, una lista que tiene x como cabeza y rest como cola) para cada valor diferente de x y rest .
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
Y, por supuesto, dado que Haskell es perezoso, la lista se genera gradualmente según sea necesario, por lo que puede evaluar parcialmente combinaciones exponencialmente grandes.
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
Aquí está mi propuesta en C ++
Traté de imponer tan poca restricción en el tipo de iterador como podría, por lo que esta solución supone simplemente iterador de reenvío, y puede ser un const_iterator. Esto debería funcionar con cualquier contenedor estándar. En los casos en que los argumentos no tienen sentido, lanza 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));
}
}
Aquí hay una implementación elegante y genérica en Scala, como se describe en 99 Problemas Scala .
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 :: _}
}
}
Aquí tienes una versión perezosa de ese algoritmo codificada en 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));
}
}
Y prueba 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 esto te ayude!
Cía#:
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
Creé una solución en SQL Server 2005 para esto y la publiqué en mi sitio web: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
Aquí hay un ejemplo para mostrar el uso:
SELECT * FROM dbo.fn_GetMChooseNCombos(''ABCD'', 2, '''')
resultados:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
Digamos que su conjunto de letras se ve así: "ABCDEFGH". Tiene tres índices (i, j, k) que indican las letras que va a utilizar para la palabra actual. Empieza con:
A B C D E F G H ^ ^ ^ i j k
Primero debes variar k, entonces el siguiente paso se ve así:
A B C D E F G H ^ ^ ^ i j k
Si llegó al final, continúe y varíe j y luego k nuevamente.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Una vez que alcanzas G, comienzas también 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 en código este look algo así.
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]);
}
}
}
Digamos que su conjunto de letras se ve así: "ABCDEFGH". Tiene tres índices (i, j, k) que indican las letras que va a utilizar para la palabra actual. Empieza con:
A B C D E F G H ^ ^ ^ i j k
Primero debes variar k, entonces el siguiente paso se ve así:
A B C D E F G H ^ ^ ^ i j k
Si llegó al final, continúe y varíe j y luego k nuevamente.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
Una vez que alcanzas G, comienzas también 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);
Basado en https://.com/a/127898/2628125 , pero más abstracto, para cualquier tamaño de punteros.
Ejemplo corto en 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 explicación, el método recursivo se describe con el siguiente ejemplo:
Ejemplo: ABCDE
Todas las combinaciones de 3 serían:
- A con todas las combinaciones de 2 del resto (BCDE).
- B con todas las combinaciones de 2 del resto (CDE)
- C con todas las combinaciones de 2 del resto (DE)
El siguiente algoritmo recursivo selecciona todas las combinaciones de elementos k de un conjunto ordenado:
- Elige el primer elemento
ide tu combinación. - combine
icon cada una de las combinaciones de elementosk-1elegidos recursivamente del conjunto de elementos más grandes quei.
Iterar lo anterior para cada i en el conjunto.
Es esencial que elija el resto de los elementos como más grandes que i , para evitar la repetición. De esta manera, [3,5] se seleccionará solo una vez, ya que [3] combinado con [5], en lugar de dos veces (la condición elimina [5] + [3]). Sin esta condición obtienes variaciones en lugar de combinaciones.
En C ++, la siguiente rutina producirá todas las combinaciones de distancia de longitud (primero, k) entre el rango [primero, último):
#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;
}
Se puede usar así:
#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;
}
Esto imprimirá lo siguiente:
123
124
125
134
135
145
234
235
245
345
Encontré este hilo útil y pensé que agregaría una solución de Javascript que pueda aparecer en Firebug. Dependiendo de su motor JS, podría tomar un poco de tiempo si la cadena de inicio es 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");
La salida debe ser la siguiente:
abc
ab
ac
a
bc
b
c
Otra versión en C # con generación perezosa de los índices de combinación. Esta versión mantiene una única serie de índices para definir una asignación entre la lista de todos los valores y los valores para la combinación actual, es decir, utiliza constantemente espacio adicional O (k) durante todo el tiempo de ejecución. El código genera combinaciones individuales, incluida la primera, en tiempo O (k) .
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 prueba:
foreach (var combination in new[] {''a'', ''b'', ''c'', ''d'', ''e''}.Combinations(3))
{
System.Console.WriteLine(String.Join(" ", combination));
}
Salida:
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
Si puede usar la sintaxis SQL, por ejemplo, si está usando LINQ para acceder a los campos de una estructura o matriz, o si accede directamente a una base de datos que tiene una tabla llamada "Alfabeto" con un solo campo de caracteres "Letra", puede adaptar lo siguiente 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
Esto devolverá todas las combinaciones de 3 letras, sin importar cuántas letras tenga en la tabla "Alfabeto" (puede ser 3, 8, 10, 27, etc.).
Si lo que desea son todas las permutaciones, en lugar de combinaciones (es decir, desea que "ACB" y "ABC" cuenten como diferentes, en lugar de aparecer una sola vez), simplemente elimine la última línea (la AND) y listo.
Edición posterior: después de volver a leer la pregunta, me doy cuenta de que lo que se necesita es el algoritmo general , no solo uno específico para el caso de seleccionar 3 elementos. La respuesta de Adam Hughes es completa, desafortunadamente no puedo votar (todavía). Esta respuesta es simple pero funciona solo cuando quieres exactamente 3 elementos.
Solución java corta:
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);
}
}
}
El 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]
Tuve un algoritmo de permutación que utilicé para el proyecto euler, en 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
Si
n<len(l)
Debes tener toda la combinación que necesites sin repetición, ¿la necesitas?
Es un generador, así que lo usas en algo como esto:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
Versión de 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))))
Y aquí viene el abuelo COBOL, el lenguaje tan difamado.
Supongamos una matriz de 34 elementos de 8 bytes cada uno (selección puramente arbitraria). La idea es enumerar todas las combinaciones posibles de 4 elementos y cargarlas en una matriz.
Utilizamos 4 índices, uno para cada posición en el grupo de 4
La matriz se procesa así:
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
Variamos idx4 desde 4 hasta el final. Para cada idx4 obtenemos una combinación única de grupos de cuatro. Cuando idx4 llega al final de la matriz, incrementamos idx3 en 1 y configuramos idx4 en idx3 + 1. Luego volvemos a ejecutar idx4 hasta el final. Procedemos de esta manera, aumentando idx3, idx2 e idx1 respectivamente hasta que la posición de idx1 sea inferior a 4 desde el final de la matriz. Eso termina el algoritmo.
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
Primeras iteraciones:
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
Un ejemplo de 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.
Art of Computer Programming Volume 4: Fascicle 3 tiene una tonelada de estos que podrían adaptarse a su situación particular mejor de lo que describo.
Códigos grises
Por supuesto, un problema con el que se encontrará es la memoria y bastante rápido, tendrá 20 problemas en su conjunto: 20 C 3 = 1140. Y si desea recorrer el conjunto, es mejor usar un gris modificado. Algoritmo de código para que no los guardes todos en la memoria. Estos generan la siguiente combinación de la anterior y evitan repeticiones. Hay muchos de estos para diferentes usos. ¿Queremos maximizar las diferencias entre combinaciones sucesivas? ¿minimizar? etcétera.
Algunos de los papeles originales que describen códigos grises:
- Algunas rutas de Hamilton y un algoritmo de cambio mínimo
- Algoritmo de generación de combinación de intercambio adyacente
Aquí hay algunos otros documentos que cubren el tema:
- Una implementación eficiente del algoritmo de generación de combinación de intercambio de lectura adyacente de Eades, Hickey (PDF, con código en Pascal)
- Generadores de combinacion
- Encuesta de códigos grises combinatorios (PostScript)
- Un algoritmo para códigos grises
Twiddle de Chase (algoritmo)
Phillip J Chase, ` Algoritmo 382: Combinaciones de M de N objetos N (1970)
Índice de combinaciones en orden lexicográfico (Algoritmo de hebillas 515)
También puede hacer referencia a una combinación por su índice (en orden lexicográfico). Al darse cuenta de que el índice debe ser una cantidad de cambio de derecha a izquierda según el índice, podemos construir algo que debería recuperar una combinación.
Entonces, tenemos un conjunto {1,2,3,4,5,6} ... y queremos tres elementos. Digamos que {1,2,3} podemos decir que la diferencia entre los elementos es de uno y en orden y mínima. {1,2,4} tiene un cambio, y es lexicográficamente el número 2. Por lo tanto, el número de ''cambios'' en el último lugar da cuenta de un cambio en el ordenamiento lexicográfico. El segundo lugar, con un cambio {1,3,4} tiene un cambio, pero representa un cambio mayor ya que está en el segundo lugar (proporcional al número de elementos en el conjunto original).
El método que he descrito es una deconstrucción, como parece, desde el conjunto hasta el índice, necesitamos hacer lo contrario, lo cual es mucho más complicado. Así es como Buckles resuelve el problema. Escribí algo de C para calcularlos , con pequeños cambios. Usé el índice de los conjuntos en lugar de un rango de números para representar el conjunto, por lo que siempre estamos trabajando desde 0 ... n. Nota:
- Como las combinaciones no están ordenadas, {1,3,2} = {1,2,3} - ordenamos que sean lexicográficas.
- Este método tiene un 0 implícito para iniciar el conjunto de la primera diferencia.
Índice de combinaciones en orden lexicográfico (McCaffrey)
Hay otra manera :, su concepto es más fácil de entender y programar, pero sin las optimizaciones de Buckles. Afortunadamente, tampoco produce combinaciones duplicadas:
El conjunto que maximiza , dónde .
Por ejemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) . Entonces, la 27ª combinación lexicográfica de cuatro cosas es: {1,2,5,6}, esos son los índices de cualquier conjunto que quieras ver. El siguiente ejemplo (OCaml), requiere la función de choose , se deja al lector:
(* 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)
https://gist.github.com/3118596
Hay una implementación para JavaScript. Tiene funciones para obtener combinaciones k y todas las combinaciones de una matriz de cualquier objeto. Ejemplos:
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]]
Algoritmo:
- Cuenta de 1 a 2 ^ n.
- Convierte cada dígito a su representación binaria.
- Convierta cada bit ''en'' a elementos de su conjunto, según la posición.
Cía#:
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();
}
}
}
¿Por qué funciona?
Existe una bijección entre los subconjuntos de un conjunto de n elementos y secuencias de n bits.
Eso significa que podemos averiguar cuántos subconjuntos hay contando secuencias.
por ejemplo, el conjunto de cuatro elementos a continuación se puede representar mediante {0,1} X {0, 1} X {0, 1} X {0, 1} (o 2 ^ 4) secuencias diferentes.
Entonces, todo lo que tenemos que hacer es contar de 1 a 2 ^ n para encontrar todas las combinaciones. (Ignoramos el conjunto vacío). Luego, traduzca los dígitos a su representación binaria. Luego sustituye los elementos de tu conjunto por bits "on".
Si solo desea resultados de k elementos, solo imprima cuando k bits estén ''activados''.
(Si desea todos los subconjuntos en lugar de los subconjuntos de longitud k, elimine la parte cnt / kElement).
(Para ver la prueba, consulte el material didáctico gratuito MIT Mathematics for Computer Science, Lehman et al, sección 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )
Aquí hay un código que escribí recientemente en Java, que calcula y devuelve toda la combinación de elementos "num" de los elementos "outOf".
// author: Sourabh Bhat ([email protected])
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 solución concisa de Javascript:
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);
Aquí hay un método que le da todas las combinaciones de tamaño especificado de una cadena de longitud aleatoria. Similar a la solución de quinmars, pero funciona para entradas variadas y k.
El código se puede cambiar para ajustarlo, es decir, ''dab'' de la entrada ''abcd'' wk = 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);
}
}
Salida para "abcde":
abc abe acd as ade bcd bce bde cde
He escrito una clase para manejar funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema al que corresponde su problema. Realiza las siguientes tareas:
Muestra todos los índices K en un formato agradable para cualquier N, elija K para un archivo. Los índices K pueden sustituirse por cadenas o letras más descriptivas. Este método hace que resolver este tipo de problema sea bastante trivial.
Convierte los índices K al índice adecuado de una entrada en la tabla de coeficientes binomiales ordenados. Esta técnica es mucho más rápida que las técnicas antiguas que se basan en la iteración. Lo hace usando una propiedad matemática inherente en el Triángulo de Pascal. Mi papel habla de esto. Creo que soy el primero en descubrir y publicar esta técnica, pero podría estar equivocado.
Convierte el índice en una tabla de coeficientes binomiales ordenados a los índices K correspondientes.
Utiliza el método de Mark Dominus para calcular el coeficiente binomial, que es mucho menos probable que se desborde y funciona con números más grandes.
La clase está escrita en .NET C # y proporciona una forma de administrar los objetos relacionados con el problema (si existe) mediante el uso de una lista genérica. El constructor de esta clase toma un valor bool llamado InitTable que, cuando verdadero, creará una lista genérica para contener los objetos que se administrarán. Si este valor es falso, entonces no creará la tabla. No es necesario crear la tabla para realizar los 4 métodos anteriores. Se proporcionan métodos de acceso para acceder a la tabla.
Hay una clase de prueba asociada que muestra cómo usar la clase y sus métodos. Ha sido probado extensivamente con 2 casos y no hay errores conocidos.
Para leer acerca de esta clase y descargar el código, vea Tablizing The Binomial Coeffieicent .
No debería ser difícil convertir esta clase a C ++.
Saltando al carro y publicando otra solución. Esta es una implementación genérica de Java. Entrada: (int k)es el número de elementos para elegir y (List<T> list)es la lista para elegir. Devuelve una lista de combinaciones (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;
}
Todo lo dicho y hecho aquí viene el código de O''caml para eso. El algoritmo es evidente a partir del 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 []
;;
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;
}
}
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;
}