Алгоритм определения возможных групп предметов

Question

Я чешу голову, пытаясь это сделать, и это съедает меня. Я знаю, что это не так сложно. У меня есть количество предметов, это число может быть больше или равно трем. Затем мне нужно определить возможную комбинацию группы предметов, которая завершит итоговое. Единственное ограничение состоит в том, что группы должны иметь три или более элементов, не превышающих (но включающих) семь элементов.

Например:

Если у меня есть 7 предметов, то у меня могут быть следующие возможные группы:

• 1 группа из 7 наименований.
• 1 группа из 4 предметов и 1 группа из 3 предметов.

Если бы у меня было 12 предметов, я мог бы иметь следующие возможные группы:

• 4 группы по 3 предмета.
• 3 группы по 4 шт.
• 2 группы по 6 шт.
• 1 группа из 7 предметов + 1 группа из 5 предметов.
• 2 группы по 3 и 1 группа по 6 наименований.
• 1 группа из 3, 1 группа из 4 и 1 группа из пяти предметов.
• ...

Я подумал о рекурсии и начал реализовывать алгоритм. Это явно не работает. Я сосу на рекурсии. Много.

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

Спасибо за помощь !!!

Answer 1

Вот алгоритм (выраженный в C ++) для решения более общей версии проблемы, с произвольными верхними и нижними границами добавлений, которые могут появляться в каждом разделе:

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

И некоторые примеры вывода:

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

Это можно сделать с помощью рекурсии.Вы не говорите, хотите ли вы просто количество возможностей или фактических возможностей.

Одна вещь, которую вы хотите сделать, - это избегать повторения, то есть значения 4 и 3 также не считаются как 3 и 4. Один из способовсделать это, чтобы создать последовательности групп не убывающих размеров.

Вероятно, лучшей структурой данных для этого является дерево:

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

Затем, чтобы найти количество комбинаций, вы просто посчитаетелистовые узлы.Чтобы найти фактические комбинации, вам нужно просто пройтись по дереву.

Алгоритм построения такого дерева выглядит примерно так:

• Функция buildTree (int size, int minSize, Tree root)
• Количество i от size до minSize;
• Создание дочернего элемента текущего узла со значением i;
• Для каждого jот minSize до i, который меньше или равен i
  • Создать нового дочернего элемента со значением j
  • Вызвать `buildTree (j, minSize, новый узел)

или что-то очень близкое к этому.

Answer 3

Я думаю, что дерево - лучший способ думать об этом, но вы можете использовать рекурсию, чтобы построить его без явного создания дерева. Вы можете думать о корне как о вашем общем количестве. Используя группы размером 3-7, вам нужно найти некоторую комбинацию групп, которая суммирует вашу общую сумму.

Вы можете использовать 0 групп по 7, 1 группу по 7, 2 группы по 7 и т. Д. Для каждого из этих значений вы можете использовать 0 групп по 6, 1 группу по 6 и т. Д. Первый уровень вашего дерева будет представлять, сколько было использовано 7. Второй уровень - это количество использованных 6 и т. Д. Когда вы используете x 7, вам необходимо выяснить, сколько комбинаций 6, 5, 4 и 3 можно использовать для суммирования до (sum-x * 7). и т. д. для каждого нижнего уровня (рекурсивный вызов).

Ваше дерево всегда будет иметь 5 уровней.

Использование рекурсии для построения дерева, вот небольшой пример кода Python (без попытки обрезки дерева, он исследует всю вещь).

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

Это выводит:

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 4

это будет число разделов из n, которые содержат только целые числа из набора [3,7]

аналогично обычной проблеме разбиения (где элементы могут быть любым положительным целым числом):

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

Я не вижу существующей числовой последовательности, которая точно соответствует этому ограничению, но вы можете сосчитать группы следующим образом (в python). это может занять произвольный диапазон (в данном случае [3,7]) и подсчитать все a, b, c, d, e (3 * a + 4 * b + 5 * c + 6 * d + 7 * e) последовательности, сумма которых равна 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)

у вас будет:

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)

или отличное решение @ Cletus

Answer 5

То, что вы описываете, является менее общей версией функции секционирования .

Алгоритмы, которые уже приведены, смехотворно сложны, вот более простой (в псевдокоде я оставляю за вами перевод на Java :))

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

Answer 6

В псевдокоде:

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

Первые два случая довольно просты.Третий, вы выясните (например), сколько существует групп размера 3 - это может быть любое число от 0 до n / 3, а затем рекурсивно с помощью функций [4, 5, 6, 7] и т. Д.