Список всех k-кортежей с записями, суммирующими n, игнорируя вращения

Question

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

Например, с k = 3 и n = 3 я бы хотел получить список, подобный следующему:

(3, 0, 0), (2, 1, 0), (2, 0, 1), (1, 1, 1).

Кортеж (0, 3, 0) не должен быть в списке, так как это ротация (3, 0, 0). Однако (0, 3, 0) может быть в списке вместо (3, 0, 0). Обратите внимание, что оба (2, 1, 0) и (2, 0, 1) находятся в списке - Я не хочу избегать всех перестановок кортежа, просто вращения . Кроме того, 0 является допустимой записью - я не ищу разделы n .

Моя текущая процедура состоит в том, чтобы выполнить цикл из более чем 1 <= <em>i <= <em>n , установить первую запись равной i , а затем рекурсивно решить проблема для n ' = n - i и k' = k - 1. Я получаю некоторую скорость -приняв обязательство, чтобы ни одна запись не была строго больше, чем первая, но этот подход все еще генерирует много вращений - например, учитывая n = 4 и k = 3, оба (2,2,0) и (2,0,2) находятся в списке вывода.

Редактировать: Добавлены пояснения жирным шрифтом. Я прошу прощения за то, что не сделал эти вопросы такими ясными, как следовало бы в оригинальном сообщении.

Answer 1

Сначала вы можете сгенерировать разделы (которые полностью игнорируют порядок) в виде кортежа (x_1, x_2, ..., x_n)

где x_i = количество раз, когда я встречаюсь.

Итак, сумма я * x_i = n.

Полагаю, вы уже знаете, как это сделать (из ваших комментариев).

Если у вас есть раздел, теперь вы можете сгенерировать для него перестановки (просматривая его как мультимножество {1,1, ..., 2,2 ..., ... n}, где i встречается x_i раз ), которые игнорируют вращения, используя ответ на этот вопрос:

Существует ли алгоритм для генерации всех уникальных циклических перестановок мультимножества?

Надеюсь, это поможет.

Answer 2

Вам нужно сгенерировать Целочисленные разделы в лексикографическом порядке.

Здесь - очень хорошая статья с быстрыми алгоритмами.

HTH.

Обратите внимание, что программы CAS обычно реализуют эти функции.Например, в Mathematica :

Innput: IntegerPartitions[10, {3}]
Output: {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, 
         {6, 2, 2}, {5, 4, 1}, {5, 3, 2}, 
         {4, 4, 2}, {4, 3, 3}}

Answer 3

Вы можете просто отсортировать свои решения и таким образом исключить повороты.
OR
вы можете попытаться создать из своего рекурсивного решения кортежи, которые будут отсортированы только

как? вот что-то я быстро выдумал

static list<tuple> tups;
void recurse(tuple l, int n, int k, int m)
{
  if (k == 0 && n == 0)
  {
    tups.add(l);
    return;
  }
  if (k == 0)
    return;

  if (k*m > n) //prunes out tuples that could not possibly be sorted
    return;
  else
    for(int x = m; x <= n; x++)
      recurse(l.add(x), n-x, k-1, x); //try only tuples that are increasing
}

вызовите это с m = 0 и пустым списком для начального шага.

вот реализация консольного приложения C #: http://freetexthost.com/b0i05jkb4e

О, я вижу свою ошибку в допущении вращения, я думал, что вы имели в виду только перестановки, а не фактическое вращение. Тем не менее, вы можете расширить мое решение для создания невращательных перестановок уникальных растущих кортежей. Я сейчас над этим работаю