Алгоритм, который дает все возможные различные массивы, чьи положительные целые элементы суммируются с данным числом

Question

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

Например, ввод 4 возвратов (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,3), (3, 1), (2,2), (4)

Не домашнее задание, а "исследование". Я просто теряюсь, пытаясь.

Кто-то, кто хорошо разбирается в комбинаторике, наверняка знает это.

Answer 1

Вот некоторая идея.

Если я не ошибаюсь, число массивов равно 2N-1, и массивы отображаются в битовые комбинации, кодирующие целые числа, образующие 0 до 2N-1-1 следующим образом:

Я покажу пример для N = 4

Первый массив - это все единицы.Представьте, что каждый бит в битовой комбинации соответствует границе между двумя ячейками массива

1 1 1 1 <- array elements
 | | |  <- sections
 0 0 0  <- bit pattern

Каждый 1 в битовой комбинации означает объединение двух соседних ячеек

1 (1+1) 1  <- array elements (1 2 1)
 |  |  |   <- sections
 0  1  0   <- bit pattern


1 (1+1+1)  <- array elements (1 3)
 |  | |    <- sections
 0  1 1    <- bit pattern


(1+1) (1+1)<- array elements (2 2)
  |  |  |  <- sections
  1  0  1  <- bit pattern


(1+1+1+1)  <- array elements (4)
  | | |    <- sections
  1 1 1    <- bit pattern

Перечислить все массивы, которые вы можетегенерировать целые числа от 0 до 2N-1-1 и для каждого полученного вами битового набора генерировать соответствующий массив.Может быть полезно преобразовать целое число в строку нулей и единиц длины N-1.Вы декодируете шаблон следующим образом:

Первая ячейка изначально содержит 1.Пройдя по шаблону слева направо, для каждого бита, если он 1, добавить 1 к текущей ячейке, если он 0, создать новую ячейку, содержащую 1.

Шаблон 1 1 0 0 1 0 1 for N = 8 будет декодирован в массив

(3 1 2 2)

Вот некоторый код C ++ без проверки аргументов и обработки шаблона справа налево.Он просто меняет порядок создаваемых массивов и его проще кодировать.

std::vector<std::vector<int> > generateArrays(unsigned int N)
{
    //validate the argument before processing
    // N > 0 and N <= numeric_limits<unsigned int>::digits

    unsigned int numOfArrays = (1U << (N-1));
    std::vector<std::vector<int> > result(numOfArrays);
    for(unsigned int i = 0; i < numOfArrays; ++i)
    {
        result[i].push_back(1);
        unsigned int mask = 1U;
        while(mask < numOfArrays)
        {
            if((i & mask) != 0)
            {
                result[i].back()++;
            }
            else
            {
               result[i].push_back(1);
            }
            mask <<= 1;
        }
    }
    return result;
}

Answer 2

Рекурсивный подход

# Pseudo code, not any real language
function all_arrays_summing_to(int N) {
    array_of_arrays All_solutions = ();
    if (N == 1) return { [[1]] }; # This is array of one array containing 1 element with value 1
    for each number x in (1 .. N-1)  {
        array_of_arrays AA = all_arrays_summing_to(N - x);
        for each array A in (AA) {
            push x onto array A;
            Add A to All_solutions;
        }
    }
    return All_solutions;
}

Answer 3

Recurse! Первая запись (назовите ее [0]) может быть любым целым числом от 1 до N. Тогда вам просто нужно найти все различные массивы положительных ненулевых целых чисел, которые складываются в N - a [0] ...

Answer 4

Возможно, это не самое элегантное решение, так как я использую «Distinct» для фильтрации дублированных результатов, но в C # есть один способ.

Общая идея состоит в том, что вы разбиваете число намассив 1, то вы просто объединяете каждый узел рядом друг с другом, как дерево, и выбираете различные комбинации.Я изобразил это так:

   [1,1,1]
   /     \
[2,1]   [1,2]
    \   /
     [3]


class Program
{
    static void Main(string[] args)
    {
        Console.Write("Enter an integer value: ");
        int num = int.Parse(Console.ReadLine());

        var y = new int[num];
        for (int x = 0; x < num; x++)
            y[x] = 1;

        var results = Combine(y, num)
            .Distinct(new ArrayComparer())
            .OrderByDescending(r => r.Length)
            .ToArray();

        foreach (var result in results)
        {
            Console.Write('[');
            for (int x = 0; x < result.Length; x++)
            {
                if (x > 0)
                    Console.Write(", ");
                Console.Write(result[x]);
            }
            Console.WriteLine(']');
        }

        Console.ReadKey(true);
    }

    public class ArrayComparer : IEqualityComparer<int[]>
    {
        bool IEqualityComparer<int[]>.Equals(int[] x, int[] y)
        {
            if (x.Length == y.Length)
            {
                for (int z = 0; z < x.Length; z++)
                    if (x[z] != y[z])
                        return false;

                return true;
            }

            return false;
        }

        int IEqualityComparer<int[]>.GetHashCode(int[] obj)
        {
            return 0;
        }
    }

    public static IEnumerable<int[]> Combine(int[] values, int num)
    {
        int val = 0;
        for (int x = 0; x < values.Length; x++)
            val += values[x];

        if (val == num)
        {
            yield return values;

            if (values.Length - 1 > 0)
            {
                for (int x = 0; x < values.Length; x++)
                {
                    int[] combined = new int[values.Length - 1];
                    for (int y = 0; y < x; y++)
                        combined[y] = values[x];

                    if (values.Length > x + 1)
                        combined[x] = values[x] + values[x + 1];

                    for (int y = x + 2; y < values.Length; y++)
                        combined[y - 1] = values[y];

                    foreach (var result in Combine(combined, num))
                        yield return result;
                }
            }
        }
    }
}

Выходы:

Enter an integer value: 4
[1, 1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[1, 1, 2]
[3, 1]
[2, 2]
[1, 3]
[4]