5个数字全排列问题，找错误


#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> permute(int nums) {
        vector<vector<int>>res;
        dfs(res, nums-1, {{nums}});
        return res;
    }
    void dfs(vector<vector<int>>& res, int num, vector<vector<int>>re) {
        if (num == 0)
            return;
        vector<vector<int>>peli;
        for (int j = 0; j < re.size(); j++) {
            vector<int>tmp= re[j];
            for (int i = 0; i < 5 - num + 1; i++) {
                tmp.insert(tmp.begin() + i, num);
                peli.push_back(tmp);
            }
        }
        dfs(res, num - 1, peli);
        if (num == 1)
            res = peli;
    }
};
int main() {
    Solution a;
    vector<vector<int>>ok;
    ok=a.permute(5);
    for (int i = 0; i < ok.size(); i++) {
        for (int j = 0; j < 5; j++) {
            cout << ok[i][j] << " ";
        }
        cout << endl;
    }
}

1-5数字全排列，我想知道我的错误在哪，运行如下

img


我就想知道我的错误在哪，

看起来你想编写一个C++程序，用于产生1到5的所有可能排列。从你提供的代码中，我找到了一些错误，并将它们纠正，以便能够正确地产生所需的全排列。

  1. dfs函数的逻辑：你的代码有一些逻辑错误，因为你没有正确地处理数字和排列的生成。

  2. 插入数字的位置：在你的dfs函数中，你尝试通过逐个插入数字来创建全排列。然而，在每次插入后，你没有将tmp恢复到其原始状态，这会导致重复插入相同的数字。

下面是一种更简单和直接的方法来生成1到5的全排列：

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(int n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        vector<vector<int>> res;
        dfs(res, nums, 0);
        return res;
    }

    void dfs(vector<vector<int>>& res, vector<int> nums, int start) {
        if (start == nums.size() - 1) {
            res.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            dfs(res, nums, start + 1);
            swap(nums[start], nums[i]); // 恢复原始状态，以便下一次交换
        }
    }
};

int main() {
    Solution a;
    vector<vector<int>> ok = a.permute(5);
    for (int i = 0; i < ok.size(); i++) {
        for (int j = 0; j < 5; j++) {
            cout << ok[i][j] << " ";
        }
        cout << endl;
    }
}

这个版本使用了典型的全排列生成方法，通过交换元素来产生每一个排列，确保每一种排列都被恰好生成一次。

img

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(int nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        vector<int> numsList;
        for (int i = 1; i <= nums; i++) {
            numsList.push_back(i);
        }
        dfs(res, numsList, tmp);
        return res;
    }

    void dfs(vector<vector<int>>& res, vector<int>& numsList, vector<int>& tmp) {
        if (tmp.size() == numsList.size()) {
            res.push_back(tmp);
            return;
        }

        for (int i = 0; i < numsList.size(); i++) {
            if (find(tmp.begin(), tmp.end(), numsList[i]) == tmp.end()) {
                tmp.push_back(numsList[i]);
                dfs(res, numsList, tmp);
                tmp.pop_back();
            }
        }
    }
};

int main() {
    Solution a;
    vector<vector<int>> ok;
    ok = a.permute(5);
    for (int i = 0; i < ok.size(); i++) {
        for (int j = 0; j < 5; j++) {
            cout << ok[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

修改了一下
如图

img


代码如下

#include <iostream>
#include <algorithm>
#include <vector>

void permute(std::vector<int>& nums) {
    do {
        for (int num : nums) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(nums.begin(), nums.end()));
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    permute(nums);
    return 0;
}

描述:
你的问题出在生成全排列的算法上。目前你的算法是固定数字1-5，然后使用嵌套循环来生成全排列。但是由于你的嵌套循环中没有对数字进行去重的操作，所以会导致重复的数字出现在排列中。

不知道你这个问题是否已经解决, 如果还没有解决的话:

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

看完这个，你绝对懂了：