for的递归

Question

我花了很长时间试图弄清楚如何去做，但它没有按预期工作；我正在编写一个代码，其中有 1 到 k 个数字，我需要找到所有可能的组合而不重复。例如对于 3：1、2、3、12、13。

用 1、2、3、4、5 计算 4 位数字的示例。

int k = 5;
for (int p = 0; p < k; p++)
{
    for (int i = p+1; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            for (int h = j + 1; h < k; h++)
            {
                cout << p + 1 << i + 1 << j + 1 << h + 1 << endl;
            }
        }
    }
}

还有 1、2、3 的 3 位数字的示例。

int k = 4
for (int p = 0; p < k; p++)
{
    for (int i = p+1; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            cout << p + 1 << i + 1 << j + 1 << endl;
        }
    }
}

我认为要在不重复的情况下计算 n 位可能的位置，我需要 n 个。而且我不知道如何在没有递归的情况下做到这一点，递归在我这样做时不起作用。我的目标是获得递归，它将计算并打印 n 位数字的可能位置。

Answer 1

我想这会让你很接近。我偶尔会在这里重复，但这应该会让你走上正确的道路。

const int max_depth = 5; // How long your string is
const int max_digit = 3; // Max digit you are counting to
int *nums = new int [max_depth];

void recurse_count(int depth)
{
    if (depth < max_depth)
    {
        for(int i = depth; i <= depth+1; i++)
        {
            nums[depth] = i;
            recurse_count(i+1);
        }
    }
    else
    {
        for (int j = 0; j < max_depth; j++)
            cout<<nums[j]+1;
        cout<<endl;
    }
}

int main()
{
    recurse_count(0);
    return 0;
}

Answer 2

我不确定递归是否是这里的最佳选择，但您可以这样做：

typedef std::vector<int> IV;
IV getFirst(int k){
    IV res;
    for (int i=0;i<k-1;i++){res.push_back(i+1);}
    return res;
}

bool getNext(IV& numbers,int i){
    if (i==-1){return false;} // end of recursion
    if (numbers[i]>i+1){return getNext(numbers,i-1);}
    numbers[i]++;
    return true;
}
bool getNext(IV& numbers){  // start of recursion
    return getNext(numbers,numbers.size()-1);
}

int main() {
    IV numbers = getFirst(5);
    for (int i=0;i<numbers.size();i++){std::cout << numbers[i];}
    std::cout << std::endl;
    while(getNext(numbers)){
        for (int i=0;i<numbers.size();i++){std::cout << numbers[i];}
        std::cout << std::endl;
    }
}

Answer 3

我自己做了递归来计算可能性，但是爱你们的所有帮助。

我的递归是

void col(int ilosc)
{
    static int st;
    for (int i = st++; i < k; i++)
    {
        if (ilosc > 1)
            col(ilosc - 1);
        else
            sposob++;
    }
}

其中 ilosc 是位数，sposob 是可能位置数的计数。

注意：sposob和k是全局变量。

Answer 4

我的方法（晚上可能还太早，我遇到了问题）

namespace detail
{
    void recurse_hlp(int min, int max, std::vector<int> vals, std::function<void(const std::vector<int>&)> f, std::size_t ptr)
    {
        if (ptr == vals.size())
            f(vals);
        else
        {
            for (int i = min; i <= max; ++i)
            {
                vals[ptr] = i;
                recurse_hlp(min, max, vals, f, ptr + 1);
            }
        }
    }
}

void recurse(int min, int max, int count, std::function<void(const std::vector<int>&)> f)
{
    std::vector<int> vals(count);
    detail::recurse_hlp(min, max, vals, f, 0);
}

void print(const std::vector<int>& vals)
{
    for (int v : vals)
        std::cout << v << " ";
    std::cout << std::endl;
}

int main()
{
    recurse(0, 5, 3, &print);
}

recurse 得到一个接受 std::vector<int> 的函数，它包含从 min 到 max 最多 count 个位置的所有数字。

for的递归

Recursion of for's

c++

recurrence