Вывести всю перестановку фиксированного числа целых чисел, которое складывается в k

Question

Предположим, у меня есть массив, инициализированный с 0 размером n.

Я хочу напечатать всю перестановку n натуральных чисел, которая складывается в натуральное число k.

Мой код на данный момент печатает только некоторые перестановки (правильные, но несколько пропущены).

Например, для n = 4 и k = 3 мой код печатает:

1 1 1 0
1 1 0 1
1 0 2 0
1 0 1 1
1 0 1 1
1 0 0 2
0 2 1 0
0 2 0 1
0 1 2 0
0 1 1 1
0 1 1 1
0 1 0 2
0 1 2 0
0 1 1 1
0 0 3 0
0 0 2 1
0 0 2 1
0 0 1 2
0 1 1 1
0 1 0 2
0 0 2 1
0 0 1 2
0 0 1 2
0 0 0 3

Вы можете видеть, что отсутствуют некоторые перестановки.Например: 3 0 0 0 и 0 3 0 0, среди прочих.

Код:

#include <iostream>

void printArray(int* a, int arraySize){
    for(int i = 0; i < arraySize; i++)
        std::cout << a[i] << " ";
    std::cout << std::endl;
}

int currentSum(int* a, int arraySize){
    int sum = 0;
    for(int i = 0; i < arraySize; i++)
        sum += a[i];
    return sum;
}

void printAll(int* a, int arraySize, int k, int beg){
    for(int i = beg; i < arraySize; i++){
        if(currentSum(a, arraySize) == k)
            printArray(a, arraySize);
        else{
            a[i]++;
            printAll(a, arraySize, k, beg+1);
            a[i]--;

        }
    }
}

int main(){
    int k = 3; //array must add up to k, exactly
    int arraySize = 4;
    int* a = new int[arraySize];
    for(int i = 0; i < arraySize; i++)
        a[i] = 0;
    printAll(a, arraySize, k, 0);
}

Answer 1

На случай, если кому-то понадобится это в будущем ...

Я последовал предложению Томаса Мэтьюса и начал искать решения, которые показывают все перестановки (с повторениями).

Я нашел этот ответ , который именно это и делает.Мне просто пришлось немного адаптировать мой код, и теперь он работает правильно.

#include <iostream>
#include <vector>

template <class Iter>
bool next_variation(Iter first, Iter last, const typename std::iterator_traits<Iter>::value_type max){
    if(first == last) return false;
    Iter i(last); --i;
    if(*i < max) { ++(*i); return true; }
    while( i != first ){
        *i = 0;
        --i;
        if(*i < max) { ++(*i); return true; }
       }
    return false;
}

void printVector(std::vector<int> a){
    for(std::vector<int>::const_iterator it = a.begin(); it!= a.end(); ++it)
        std::cout << *it << " ";
    std::cout << std::endl;
}

int currentSum(std::vector<int> a){
    int sum = 0;
    for(std::vector<int>::const_iterator it = a.begin(); it!= a.end(); ++it)
        sum += *it;
    return sum;
}

void printAll(std::vector<int> a, int k){
    do{
        if(currentSum(a) == k)
            printVector(a);
      }
    while( next_variation(a.begin(), a.end(), a.size()) );
}

int main(){
    int k = 3; //array must add up to k, exactly
    int arraySize = 4;

    std::vector<int> a(arraySize,0); // Initialized with 0
    printAll(a, k);

}

И вывод:

0 0 0 3
0 0 1 2
0 0 2 1
0 0 3 0
0 1 0 2
0 1 1 1
0 1 2 0
0 2 0 1
0 2 1 0
0 3 0 0
1 0 0 2
1 0 1 1
1 0 2 0
1 1 0 1
1 1 1 0
1 2 0 0
2 0 0 1
2 0 1 0
2 1 0 0
3 0 0 0

, как и ожидалось.

Answer 2

Вы увеличиваете только a[0] один раз , потому что только первый вызов printAll будет иметь значение beg, равное 0. a[1] может быть увеличено в два раза, a[2] в три раза,и т. д.

Вам нужно изменить цикл в printAll, чтобы иметь возможность увеличивать a[i] несколько раз.