Далее Состав n на k частей - у кого-нибудь работает алгоритм

Question

Состав n в k частей - я хочу перечислить все возможные составы n в k частей - у кого-нибудь есть алгоритм (предпочтительно в R)? Или знаете, где-нибудь в библиотеке?

Например, если у меня есть n кубов и k сумок, и я хочу перечислить все возможные расположения кубиков в сумках. например Есть 3 способа, которыми вы можете расположить 2 кубика в 2 мешка:

(2, 0) (1, 1) (0, 2)

Я нашел алогарифм NEXCOM. Я нашел его версию здесь (стр. 46) на Фортране, но не пишите код на Фортране, так что вы действительно понимаете, что происходит - любая помощь?

Answer 1

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

def weak_compositions(boxes, balls, parent=tuple()):
  if boxes > 1:
    for i in xrange(balls + 1):
      for x in weak_compositions(boxes - 1, i, parent + (balls - i,)):
        yield x
  else:
    yield parent + (balls,)

тест:

>>> for x in weak_compositions(3, 5): print x
(5, 0, 0)
(4, 1, 0)
(4, 0, 1)
(3, 2, 0)
...
(0, 1, 4)
(0, 0, 5)

Answer 2

То, что вы пытаетесь перечислить, называется k -милликомбинацией. Проблема часто формулируется так: учитывая n неразличимых шаров и k ящиков, перечислите все возможные способы распределения всех шаров в ящиках. Количество таких распределений:

factorial(n + k - 1) / (factorial(k - 1) * factorial(n))

Дополнительную информацию см. В методе 4 из Двенадцатикратного пути .

Вот код для перечисления распределений (C ++):

string & ListMultisets(unsigned au4Boxes, unsigned au4Balls, string & strOut = string ( ), string strBuild = string ( ))
{
    unsigned au4;
    if (au4Boxes > 1) for (au4 = 0; au4 <= au4Balls; au4++)
    {
        stringstream ss;
        ss << strBuild << (strBuild.size() == 0 ? "" : ",") << au4Balls - au4;
        ListMultisets (au4Boxes - 1, au4, strOut, ss.str ( ));
    }
    else
    {
        stringstream ss;
        ss << "(" << strBuild << (strBuild.size() == 0 ? "" : ",") << au4Balls << ")\n";
        strOut += ss.str ( );
    }
    return strOut;
}



int main(int argc, char * [])
{    
    cout << endl << ListMultisets (3, 5) << endl;
    return 0;
}

Вот вывод из вышеприведенной программы (5 шаров, распределенных по трем коробкам):

(5,0,0)
(4,1,0)
(4,0,1)
(3,2,0)
(3,1,1)
(3,0,2)
(2,3,0)
(2,2,1)
(2,1,2)
(2,0,3)
(1,4,0)
(1,3,1)
(1,2,2)
(1,1,3)
(1,0,4)
(0,5,0)
(0,4,1)
(0,3,2)
(0,2,3)
(0,1,4)
(0,0,5)

Answer 3

Вычислительные композиции (я игнорирую, насколько стандартным является этот термин) и комбинации в некотором смысле эквивалентны. Существует биективная функция между комбинациями k + 1 в n + k и композициями n в k частях. Все, что нужно сделать, это присвоить число от 1 до n каждой букве комбинаций, упорядочить буквы в соответствии с их номером, затем:

• создать кортеж, составленный из различий между числами последовательных букв
• вычтите 1 на каждую запись в кортеже, и вот оно у вас.

Если ваш алгоритм вычисления комбинаций дает комбинации с «упорядоченными буквами», то остальное - тривиальное вычисление.

В Python:

<code>from itertools import combinations, tee 
  #see: 
  #http://docs.python.org/library/itertools.html#itertools.combinations
  #http://docs.python.org/library/itertools.html#itertools.tee</p>

<p>def diffed_tuple(t):
    # return a new tuple but where the entries are the differences
    # between consecutive entries of the original tuple.
    #make two iterator objects which yield entries from t in parallel
    t2, t1 = tee(t)
    # advance first iterator one step
    for x in t2:
        break
    # return a tuple made of the entries yielded by the iterators
    return tuple(e2 - e1 for e2, e1 in zip(t2, t1))</p>

<p># --The Algorithm--
def compositions(n, k):
    for t in combinations(range(n+k), k+1):
        # yield the 'diffed tuple' but subtracting 1 from each entry
        yield tuple(e-1 for e in diffed_tuple(t))

Answer 4

Я сделал перевод оригинального алгоритма NEXCOM на структурированный фортран и Java. Версия Java:

public void allCombinations(final int n, final int k) {
    final int[] input = new int[k + 1];
    Boolean mtc = Boolean.FALSE;
    int t = n;
    int h = 0;
    do {
        if (mtc) {
            if (t > 1) {
                h = 0;
            }
            h++;
            t = input[h];
            input[h] = 0;
            input[1] = t - 1;
            input[h + 1]++;
        } else {
            // First permutation is always n00...0 i.e. it's a descending
            // series lexicographically.
            input[1] = n;
            for (int i = 2; i <= k; i++) {
                input[i] = 0;
            }
        }
        System.out.println(java.util.Arrays.toString(input));
        mtc = input[k] != n;
    } while (mtc);
}