Algoritmo per determinare possibili gruppi di articoli

Question

Mi sto grattando la testa cercando di fare questo e mi sta divorando. So che non è così complesso. Ho un numero di elementi, questo numero può essere uguale o maggiore di tre. Quindi ho bisogno di determinare la possibile combinazione di un gruppo di elementi che completerà il totale. L'unica limitazione è che i gruppi dovrebbero avere tre o più elementi, non eccedere (ma includere) sette elementi.

Ad esempio:

Se Ho 7 elementi, quindi ho potuto avere queste possibili gruppi:

• 1 gruppo di 7 elementi.
• 1 gruppo di 4 articoli e 1 gruppo di 3 articoli.

Se ho 12 articoli, ho potuto avere questi possibili gruppi:

• 4 gruppi di 3 elementi.
• 3 gruppi di 4 articoli.
• 2 gruppi di 6 articoli.
• 1 gruppo di 7 articoli + 1 gruppo di 5 articoli.
• 2 gruppi di 3 e 1 gruppo di 6 articoli.
• 1 gruppo di 3, 1 gruppo di 4 e 1 gruppo di cinque articoli.
• ...

ho pensato di ricorsione e iniziato ad attuare l'algoritmo. Ovviamente non funziona. Faccio schifo alla ricorsione. Un sacco.

//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); 
       } 
      } 
     } 
    } 
} 

Grazie per il vostro aiuto !!!

Answer 1

Ecco un algoritmo (espressa in C++) per risolvere una versione più generale del problema, con limiti superiori e inferiori arbitrarie sugli addendi eventualmente presenti in ciascun partizione:

#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); 
} 

E alcuni di campionamento di uscita:

$ ./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

questo sarebbe il numero di partitions di n che contengono solo numeri interi dal set [3,7]

simile al problema partizione regolare (dove gli elementi possono essere un numero intero positivo):

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

Non vedo una sequenza numerica esistente che corrisponda esattamente a questo vincolo, ma è possibile contare i gruppi in questo modo (in python). questo può richiedere un range arbitrario ([3,7] in questo caso) e contare tutti i a, b, c, d, e (3 * a + 4 * b + 5 * c + 6 * d + 7 * e) sequenze che sommano 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) 

dovreste:

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 @ eccellente soluzione di Cletus

Answer 3

può essere fatto con la ricorsione. Non dici se vuoi solo il numero di possibilità o le possibilità reali.

Una cosa che si vuole fare è evitare il significato della ripetizione, non contare 4 e 3 anche come 3 e 4. Un modo per farlo è creare sequenze di gruppi di dimensioni non discendenti.

Probabilmente la migliore struttura dati per questo è un albero:

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

quindi per individuare il numero di combinazioni è sufficiente contare i nodi foglia. Per trovare le combinazioni attuali, basta camminare sull'albero.

L'algoritmo per la costruzione di un tale albero va qualcosa di simile:

• Funzione buildTree (int size, int minSize, Radice di albero)
• Conte i da size fino a minSize;
• Creare un figlio del nodo corrente con valore i;
• Per ogni jminSize-i che è minore o uguale a i
  • Creare un nuovo figlio di valore j
  • chiamata `buildTree (j, minSize, nuovo nodo)

o qualcosa di molto vicino a quello.

Answer 4

Un albero è il modo migliore di pensarci, penso, ma è possibile utilizzare la ricorsione per crearne uno senza fare esplicitamente un albero. Puoi pensare alla radice come al totale. Utilizzando gruppi di dimensioni 3-7, è necessario trovare alcune combinazioni di gruppi che si sommano al totale.

Puoi usare 0 gruppi di 7, 1 gruppo di 7, 2 gruppi di 7, ecc. Per ciascuno di questi valori, puoi usare 0 gruppi di 6, 1 gruppo di 6, ecc. Il primo livello del tuo l'albero rappresenterà il numero di 7 utilizzati. Il secondo livello è il numero di 6 utilizzati, ecc. Quando usi x 7, devi capire quante combinazioni di 6, 5, 4 e 3 puoi usare per sommare fino a (sum-x * 7) e così via per ogni livello inferiore (chiamata ricorsiva).

Il tuo albero avrà sempre 5 livelli.

Utilizzando la ricorsione per costruire l'albero, ecco un piccolo esempio di codice Python (senza alcun tentativo di potare l'albero, esplorerà l'intera cosa).

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, "") 

This uscite:

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

In pseudocodice:

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); 
     } 
    } 
} 

I primi due casi sono abbastanza straight-forward.Il terzo, capisci (per esempio) quanti gruppi di dimensione 3 ci sono - che possono essere qualsiasi numero compreso tra 0 e n/3, e quindi ricorsivamente la funzione con [4, 5, 6, 7], ecc.

Answer 6

Quello che stai descrivendo è una versione meno generale di partition function.

Gli algoritmi già date sono ridicolmente complicata, ecco un uno più semplice (in pseudo-codice, io lascio a voi di tradurre in Java :))

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