Algoritmo para determinar posibles grupos de elementos

Question

Me estoy rascando la cabeza tratando de hacer esto y me está comiendo. Sé que no es TAN complejo. Tengo varios artículos, este número puede ser igual o mayor a tres. Entonces necesito determinar la combinación posible de grupo de elementos que completará el total. La única restricción es que los grupos deben tener tres o más elementos, sin exceder (pero incluir) siete elementos.

Por ejemplo:

Si tengo 7 artículos, entonces podría tener estos posibles grupos:

• 1 grupo de 7 elementos.
• 1 grupo de 4 elementos y 1 grupo de 3 elementos.

Si tengo 12 artículos, que podría tener estos posibles grupos:

• 4 grupos de 3 elementos.
• 3 grupos de 4 elementos.
• 2 grupos de 6 elementos.
• 1 grupo de 7 elementos + 1 grupo de 5 elementos.
• 2 grupos de 3 y 1 grupo de 6 elementos.
• 1 grupo de 3, 1 grupo de 4 y 1 grupo de cinco elementos.
• ...

pensé en la recursividad y empezó a ejecutar el algoritmo. Obviamente no está funcionando. Yo chupo en la recursión. Mucho.

//Instance Fields 
public List<ArrayList<String>> options; 

//Method that will generate the options. The different options are 
//stored in a list of "option". An individual option will store a list of 
//strings with the individual groups. 
public void generateOptions(int items, ArrayList<String> currentOption){ 

    //If the current option is null, then create a new option. 
    if(currentOption == null){ 
     currentOption = new ArrayList<String>(); 
    } 
    if(items < 3){ 
     //If the number of items is less than three then it doesn't comply with the 
     //requirements (teams should be more or equal than three. 
     currentOption.add("1 group of "+items+" items"); 
     options.add(currentOption); 
    } 
    else{ 
     //I can make groups of 3,4,5,6 and 7 items. 
     for(int i = 3;i<=7;i++){ 
      if(items%i == 0){ 
       // If the number of items is divisible per the current number, 
       // then a possible option could be items/i groups of i items. 
       // Example: Items = 9. A possible option is 3 groups of 3 items. 
       currentOption.add(items/i +" groups of "+ i+" items"); 
       options.add(currentOption); 
      } 
      else{ 
       // If the number of items - the current number is equal or greater than 
       // three, then a possible option could be a group of i items 
       // and then I'll have items-i items to separate in other groups. 
       if(items - i >=3){ 
        currentOption.add("1 group of "+i+" items"); 
        generateOptions(items-i,currentOption); 
       } 
      } 
     } 
    } 
} 

Gracias por su ayuda !!!

Answer 1

Aquí está un algoritmo (expresado en C++) para resolver una versión más general del problema, con límites superior e inferior arbitrarios en los sumandos que pueden aparecer en cada partición:

#include <iostream> 
#include <vector> 

using namespace std; 

typedef vector<int> Partition; 
typedef vector<Partition> Partition_list; 

// Count and return all partitions of an integer N using only 
// addends between min and max inclusive. 

int p(int min, int max, int n, Partition_list &v) 
{ 
    if (min > max) return 0; 
    if (min > n) return 0;  
    if (min == n) { 
     Partition vtemp(1,min); 
     v.push_back(vtemp); 
     return 1; 
    } 
    else { 
    Partition_list part1,part2; 
    int p1 = p(min+1,max,n,part1); 
    int p2 = p(min,max,n-min,part2); 
    v.insert(v.end(),part1.begin(),part1.end()); 
    for(int i=0; i < p2; i++) 
    { 
     part2[i].push_back(min); 
    } 
    v.insert(v.end(),part2.begin(),part2.end()); 
    return p1+p2; 
    } 
} 

void print_partition(Partition &p) 
{ 
    for(int i=0; i < p.size(); i++) { 
     cout << p[i] << ' '; 
    } 
    cout << "\n"; 
} 

void print_partition_list(Partition_list &pl) 
{ 
    for(int i = 0; i < pl.size(); i++) { 
     print_partition(pl[i]); 
    } 
} 

int main(int argc, char **argv) 
{ 
    Partition_list v_master; 

    int n = atoi(argv[1]); 
    int min = atoi(argv[2]); 
    int max = atoi(argv[3]); 
    int count = p(min,max,n,v_master); 
    cout << count << " partitions of " << n << " with min " << min ; 
    cout << " and max " << max << ":\n" ; 
    print_partition_list(v_master); 
} 

Y algunos de muestreo de salida:

$ ./partitions 12 3 7    
6 partitions of 12 with min 3 and max 7: 
6 6 
7 5 
4 4 4 
5 4 3 
6 3 3 
3 3 3 3 
$ ./partitions 50 10 20    
38 partitions of 50 with min 10 and max 20: 
17 17 16 
18 16 16 
18 17 15 
19 16 15 
20 15 15 
18 18 14 
19 17 14 
20 16 14 
19 18 13 
20 17 13 
19 19 12 
20 18 12 
13 13 12 12 
14 12 12 12 
20 19 11 
13 13 13 11 
14 13 12 11 
15 12 12 11 
14 14 11 11 
15 13 11 11 
16 12 11 11 
17 11 11 11 
20 20 10 
14 13 13 10 
14 14 12 10 
15 13 12 10 
16 12 12 10 
15 14 11 10 
16 13 11 10 
17 12 11 10 
18 11 11 10 
15 15 10 10 
16 14 10 10 
17 13 10 10 
18 12 10 10 
19 11 10 10 
20 10 10 10 
10 10 10 10 10 

Answer 2

este sería el número de partitions de n que contiene sólo números enteros del conjunto [3,7]

similar al problema de partición regular (donde los elementos pueden ser cualquier número entero positivo):

http://www.research.att.com/~njas/sequences/A000041

no veo una secuencia numérica existente que coincida exactamente con esta restricción, pero puede contar los grupos como tal (en python). esto puede tomar un rango arbitrario ([3,7] en este caso) y contar todas las a, b, c, d, e (3 * a + 4 * b + 5 * c + 6 * d + 7 * e) secuencias que se suman a n.

import sys 

# All partitions for a particular n: 

def groups(n, base, minBase, sum, sets, group = []): 
    c = 0; i = (n - sum)/base 
    while i >= 0: 
    s = sum + base * i 
    if s == n: 
     sets.append(group + [i]); 
     c = c + 1 
    elif s < n and base > minBase: 
     c = c + groups(n, base - 1, minBase, s, sets, (group + [i])) 
    i = i - 1 
    return c 

# Partitions for each n in [1,maxNum] 

def run(maxNum): 
    for i in xrange(1, maxNum + 1): 
    sets = []; maxBase = 7; minBase = 3 
    n = groups(i, maxBase, minBase, 0, sets) 
    print ' %d has %d groups:\n' % (i, n) 
    for g in sets: 
     x = len(g) - 1 
     sys.stdout.write('  ') 
     while x >= 0: 
     if g[x] > 0: 
      if x < len(g) - 1: sys.stdout.write(' + ') 
      sys.stdout.write('(%d * %d)' % (maxBase - x, g[x])) 
     x = x - 1 
     print '' 
    if len(sets): print '' 

run(40) 

que tendría:

1 has 0 groups: 

2 has 0 groups: 

3 has 1 groups: 

    (3 * 1) 

4 has 1 groups: 

    (4 * 1) 

5 has 1 groups: 

    (5 * 1) 

6 has 2 groups: 

    (6 * 1) 
    (3 * 2) 

7 has 2 groups: 

    (7 * 1) 
    (3 * 1) + (4 * 1) 

8 has 2 groups: 

    (3 * 1) + (5 * 1) 
    (4 * 2) 

9 has 3 groups: 

    (3 * 1) + (6 * 1) 
    (4 * 1) + (5 * 1) 
    (3 * 3) 

10 has 4 groups: 

    (3 * 1) + (7 * 1) 
    (4 * 1) + (6 * 1) 
    (5 * 2) 
    (3 * 2) + (4 * 1) 

11 has 4 groups: 

    (4 * 1) + (7 * 1) 
    (5 * 1) + (6 * 1) 
    (3 * 2) + (5 * 1) 
    (3 * 1) + (4 * 2) 

12 has 6 groups: 

    (5 * 1) + (7 * 1) 
    (6 * 2) 
    (3 * 2) + (6 * 1) 
    (3 * 1) + (4 * 1) + (5 * 1) 
    (4 * 3) 
    (3 * 4) 

13 has 6 groups: 

    (6 * 1) + (7 * 1) 
    (3 * 2) + (7 * 1) 
    (3 * 1) + (4 * 1) + (6 * 1) 
    (3 * 1) + (5 * 2) 
    (4 * 2) + (5 * 1) 
    (3 * 3) + (4 * 1) 

14 has 7 groups: 

    (7 * 2) 
    (3 * 1) + (4 * 1) + (7 * 1) 
    (3 * 1) + (5 * 1) + (6 * 1) 
    (4 * 2) + (6 * 1) 
    (4 * 1) + (5 * 2) 
    (3 * 3) + (5 * 1) 
    (3 * 2) + (4 * 2) 

15 has 9 groups: 

    (3 * 1) + (5 * 1) + (7 * 1) 
    (4 * 2) + (7 * 1) 
    (3 * 1) + (6 * 2) 
    (4 * 1) + (5 * 1) + (6 * 1) 
    (3 * 3) + (6 * 1) 
    (5 * 3) 
    (3 * 2) + (4 * 1) + (5 * 1) 
    (3 * 1) + (4 * 3) 
    (3 * 5) 

o @ excelente solución de Cletus

Answer 3

se puede hacer con la recursividad. No dices si solo quieres el número de posibilidades o las posibilidades reales.

Una cosa que quiere hacer es evitar la repetición, es decir, no cuente 4 y 3 también como 3 y 4. Una forma de hacerlo es crear secuencias de tamaños de grupos no descendentes.

Probablemente la mejor estructura de datos para esto es un árbol:

root 
+- 12 
+- 9 
| +- 3 
+- 8 
| +- 4 
+- 7 
| +- 5 
+- 6 
| +- 6 
| +- 3 
|  +- 3 
+- 5 
| +- 4 
|  +- 3 
+- 4 
| +- 4 
|  +- 4 
+- 3 
    +- 3 
     +- 3 
     +- 3 

A continuación, para encontrar el número de combinaciones que simplemente contar los nodos hoja. Para encontrar las combinaciones reales, simplemente camina por el árbol.

El algoritmo para la construcción de un árbol de tal o menos así:

• Función buildTree (tamaño, int minSize, la raíz del árbol)
• i conde de size a minSize;
• Cree un elemento secundario del nodo actual con el valor i;
• Para cada jminSize-i que es menor que o igual a i
  • Crear un nuevo niño de valor j
  • Call `buildTree (j, minSize, nuevo nodo)

o algo muy parecido a eso.

Answer 4

Un árbol es la mejor manera de pensarlo, creo, pero puede usar la recursión para compilar uno sin crear explícitamente un árbol. Puedes pensar en la raíz como tu total. Usando grupos de tamaño 3-7, necesita encontrar una combinación de grupos que sume hasta su total.

Puede usar 0 grupos de 7, 1 grupo de 7, 2 grupos de 7, etc. Para cada uno de esos valores, puede usar 0 grupos de 6, 1 grupo de 6, etc. El primer nivel de su el árbol representará cuántos 7 se usaron. El segundo nivel es cuántos de 6 se usaron, etc. Cuando usa x 7, necesita calcular cuántas combinaciones de 6, 5, 4 y 3 puede usar para sumar (suma-x * 7) , y así sucesivamente para cada nivel inferior (llamada recursiva).

Su árbol siempre tendrá 5 niveles.

Usando recursión para construir el árbol, aquí hay una pequeña muestra de código de Python (sin intentar podar el árbol, explorará todo).

MIN = 3 
MAX = 7 

def findComb(remaining, start, path): 
    times = remaining/start 

    if start == MIN: 
     if remaining % MIN == 0: 
      print "%s, %d %d's" % (path[1:], times, start) 
     return 

    for i in range(0, times+1): 
     findComb(remaining- (i*start), start-1, "%s, %d %d's" % (path, i, start)) 


findComb(12, MAX, "") 

Este salidas:

0 7's, 0 6's, 0 5's, 0 4's, 4 3's 
0 7's, 0 6's, 0 5's, 3 4's, 0 3's 
0 7's, 0 6's, 1 5's, 1 4's, 1 3's 
0 7's, 1 6's, 0 5's, 0 4's, 2 3's 
0 7's, 2 6's, 0 5's, 0 4's, 0 3's 
1 7's, 0 6's, 1 5's, 0 4's, 0 3's 

Answer 5

En pseudocódigo:

List<String> results; 

void YourAnswer(int n) { 
    GeneratePossiblities("", [3, 4, 5, 6, 7], n); 
} 

void GeneratePossibilities(String partialResult, List<int> buildingBlocks, int n) { 
    if (n == 0) { 
     // We have a solution 
     results.Add(partialResult); 
    } else if (buildingBlocks.IsEmpty()) { 
     // Dead-end: there is no solution that starts with the partial result we have and contains only the remaining building blocks 
     return; 
    } else { 
     int first = buildingBlocks.First(); 
     buildingBlocks.PopFirst(); 
     for (int i = 0, i < n/first; i++) { 
      GeneratePossibilities(partialResult + " " + i + "groups of " + first, 
           buildingBlocks, 
           n - i * first); 
     } 
    } 
} 

Los dos primeros casos son bastante sencilla.El tercero, averigua (por ejemplo) cuántos grupos de tamaño 3 hay, que puede ser cualquier número entre 0 y n/3, y luego recursivamente la función con [4, 5, 6, 7], etc.

Answer 6

Lo que está describiendo es una versión menos general de partition function.

Los algoritmos ya dadas son ridículamente complicado, aquí es un simple (en pseudo-código, lo dejaré hasta que traducir a Java :))

p(min, n): 
    if min > n: return 0 
    if min = n: return 1 
    return p(min+1, n) + p(min, n-min)