algorithm - todas - permutacion de numeros en c++
¿Algoritmo para generar todas las permutaciones únicas de particiones enteras de longitud fija? (6)
Estoy buscando un algoritmo que genere todas las permutaciones de particiones de longitud fija de un entero. El orden no importa.
Por ejemplo, para n = 4 y longitud L = 3:
[(0, 2, 2), (2, 0, 2), (2, 2, 0),
(2, 1, 1), (1, 2, 1), (1, 1, 2),
(0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3),
(0, 0, 4), (4, 0, 0), (0, 4, 0)]
Me equivoqué con particiones enteras + permutaciones para particiones cuya longitud es menor que L; pero eso fue demasiado lento porque obtuve la misma partición varias veces (porque [0, 0, 1] puede ser una permutación de [0, 0, 1] ;-)
Cualquier ayuda apreciada, y no, esto no es tarea, interés personal :-)
Bueno. Primero, olvídese de las permutaciones y solo genere las particiones de longitud L (como lo sugiere @Svein Bringsli). Tenga en cuenta que para cada partición, puede imponer un orden en los elementos, como>. Ahora solo "cuente", manteniendo su orden. Para n = 4, k = 3:
(4, 0, 0)
(3, 1, 0)
(2, 2, 0)
(2, 1, 1)
Entonces, ¿cómo implementar esto? Parece que: al restar 1 de la posición i y agregarlo a la siguiente posición mantiene nuestro orden, resta 1 de la posición i, agrega 1 a la posición i + 1, y avanza a la siguiente posición. Si estamos en la última posición, retrocede.
Aquí hay un pequeño pitón que hace justamente eso:
def partition_helper(l, i, result):
if i == len(l) - 1:
return
while l[i] - 1 >= l[i + 1] + 1:
l[i] -= 1
l[i + 1] += 1
result.append(list(l))
partition_helper(l, i + 1, result)
def partition(n, k):
l = [n] + [0] * (k - 1)
result = [list(l)]
partition_helper(l, 0, result)
return result
Ahora tiene una lista de listas (realmente una lista de multisecuencias) y generar todas las permutaciones de cada multiset de la lista le brinda su solución. No voy a entrar en eso, hay un algoritmo recursivo que básicamente dice que, para cada posición, elija cada elemento único en el conjunto múltiple y anexe las permutaciones del conjunto múltiple resultante de eliminar ese elemento del conjunto múltiple.
Dado que usted pregunta esto por interés, ¡probablemente le interese una respuesta autoritaria! Se puede encontrar en "7.2.1.2 - Generando todas las permutaciones" del Knuth''s The Art of Computer Programming ( subvolumen 4A ).
Además, 3 algoritmos concretos se pueden encontrar aquí .
Como mencioné anteriormente, no pude hacer que el código de @rlibby funcionara para mis necesidades, y necesitaba código donde n = l, por lo que solo un subconjunto de su necesidad. Aquí está mi código a continuación, en C #. Sé que no es una respuesta perfecta a la pregunta anterior, pero creo que solo tendrías que modificar el primer método para hacerlo funcionar con diferentes valores de l; Básicamente, agregue el mismo código que @rlibby, haciendo la matriz de longitud l en vez de longitud n.
public static List<int[]> GetPartitionPermutations(int n)
{
int[] l = new int[n];
var results = new List<int[]>();
GeneratePermutations(l, n, n, 0, results);
return results;
}
private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results)
{
if (n == 0)
{
for (; i < l.Length; ++i)
{
l[i] = 0;
}
results.Add(l.ToArray());
return;
}
for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt)
{
l[i] = cnt;
GeneratePermutations(l, (n - cnt), cnt, i + 1, results);
}
}
Como señaló @pbarranis, el código de @rlibby no incluye todas las listas cuando n es igual a k . Debajo está el código de Python que incluye todas las listas. Este código no es recursivo, lo que puede ser más eficiente con respecto al uso de la memoria.
def successor(n, l):
idx = [j for j in range(len(l)) if l[j] < l[0]-1]
if not idx:
return False
i = idx[0]
l[1:i+1] = [l[i]+1]*(len(l[1:i+1]))
l[0] = n - sum(l[1:])
return True
def partitions(n, k):
l = [0]*k
l[0] = n
results = []
results.append(list(l))
while successor(n, l):
results.append(list(l))
return results
Las listas se crean en orden colexicográfico (algoritmo y más descripción aquí ).
Una gran cantidad de búsquedas llevó a esta pregunta. Aquí hay una respuesta que incluye las permutaciones:
#!/usr/bin/python
from itertools import combinations_with_replacement as cr
def all_partitions(n, k):
"""
Return all possible combinations that add up to n
i.e. divide n objects in k DISTINCT boxes in all possible ways
"""
all_part = []
for div in cr(range(n+1), k-1):
counts = [div[0]]
for i in range(1, k-1):
counts.append(div[i] - div[i-1])
counts.append(n-div[-1])
all_part.append(counts)
return all_part
Por ejemplo, all_part (4, 3) según lo solicitado por OP da:
[[0, 0, 4],
[0, 1, 3],
[0, 2, 2],
[0, 3, 1],
[0, 4, 0],
[1, 0, 3],
[1, 1, 2],
[1, 2, 1],
[1, 3, 0],
[2, 0, 2],
[2, 1, 1],
[2, 2, 0],
[3, 0, 1],
[3, 1, 0],
[4, 0, 0]]
Descubrí que usar una función recursiva no era bueno para longitudes y enteros más grandes porque mastica demasiada RAM, y el uso de un generador / función reanudable (que ''cede'' valores) era demasiado lento y requería una gran biblioteca para hacerlo cruzar -plataforma.
Así que aquí hay una solución no recursiva en C ++ que produce las particiones en orden ordenado (que también es ideal para las permutaciones). He descubierto que es 10 veces más rápido que las soluciones recursivas aparentemente inteligentes y concisas que probé para longitudes de partición de 4 o más, pero para longitudes de 1-3 el rendimiento no es necesariamente mejor (y no me importa el corto longitudes porque son rápidos con cualquier enfoque).
// Inputs
unsigned short myInt = 10;
unsigned short len = 3;
// Partition variables.
vector<unsigned short> partition(len);
unsigned short last = len - 1;
unsigned short penult = last - 1;
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3.
unsigned short sum = 0;
// Prefill partition with 0.
fill(partition.begin(), partition.end(), 0);
do {
// Calculate remainder.
partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints.
/*
*
* DO SOMETHING WITH "partition" HERE.
*
*/
if (partition[cur + 1] <= partition[cur] + 1) {
do {
cur--;
} while (
cur > 0 &&
accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt
);
// Escape if seeked behind too far.
// I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3.
if (cur < 0) {
break;
}
// Increment the new cur position.
sum++;
partition[cur]++;
// The value in each position must be at least as large as the
// value in the previous position.
for (unsigned short i = cur + 1; i < last; ++i) {
sum = sum - partition[i] + partition[i - 1];
partition[i] = partition[i - 1];
}
// Reset cur for next time.
cur = penult;
}
else {
sum++;
partition[penult]++;
}
} while (myInt - sum >= partition[penult]);
Donde escribí HAGA ALGO CON "partición" AQUÍ. es donde realmente consumirías el valor. (En la última iteración, el código continuará ejecutando el resto del ciclo pero encontré que esto es mejor que verificar constantemente las condiciones de salida; está optimizado para operaciones más grandes)
0,0,10 0,1,9 0,2,8 0,3,7 0,4,6 0,5,5 1,1,8 1,2,7 1,3,6 1,4,5 2,2,6 2,3,5 2,4,4 3,3,4
Oh, he usado "unsigned short" porque sé que mi longitud y número entero no excederán ciertos límites, cámbialo si no es adecuado para ti :) Revisa los comentarios; una variable allí (cur) tuvo que estar firmada para manejar longitudes de 1 o 2 y hay una instrucción if correspondiente que va con eso, y también he notado en un comentario que si su vector de partición tiene entradas firmadas hay otra línea eso se puede simplificar
Para obtener todas las composiciones, en C ++ usaría esta estrategia de permutación simple que afortunadamente no produce ningún duplicado:
do {
// Your code goes here.
} while (next_permutation(partition.begin(), partition.end()));
Nido que en el HACER ALGO CON "partición" AQUÍ , y estás listo para ir.
Una alternativa para encontrar las composiciones (basadas en el código de Java aquí https://www.nayuki.io/page/next-lexicographical-permutation-algorithm ) es la siguiente. He encontrado que funciona mejor que next_permutation ().
// Process lexicographic permutations of partition (compositions).
composition = partition;
do {
// Your code goes here.
// Find longest non-increasing suffix
i = last;
while (i > 0 && composition[i - 1] >= composition[i]) {
--i;
}
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0) {
break;
}
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
j = last;
while (composition[j] <= composition[i - 1])
--j;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
temp = composition[i - 1];
composition[i - 1] = composition[j];
composition[j] = temp;
// Reverse the suffix
j = last;
while (i < j) {
temp = composition[i];
composition[i] = composition[j];
composition[j] = temp;
++i;
--j;
}
} while (true);
Notarás algunas variables no declaradas allí, solo debes declararlas antes en el código antes de todos tus ciclos de do: i , j , pos y temp (cortos sin firmar), y composition (el mismo tipo y longitud que la partition ). Puede reutilizar la declaración de i para su uso en un bucle for en el fragmento de código de particiones. También tenga en cuenta variables como la last se usa, que asume que este código está anidado dentro del código de particiones dado anteriormente.
Nuevamente, "Tu código va aquí" es donde consumes la composición para tus propios fines.
Para referencia aquí están mis encabezados.
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;
A pesar del aumento masivo de la velocidad con estos enfoques, para cualquier número entero considerable y longitud de partición esto todavía te enojará con tu CPU :)