c++ - 蛮力排列交换

Question

我一直在研究一种强力算法来生成给定集合的所有排列。最后，我想将这些排列中的每一个都输入到一个 nxn 矩阵中，以测试它是否是一个有效的幻方。--我知道有一种方法可以轻松生成魔方--不过，那不是我想做的。我专注于它的蛮力方面。

对于一组 3 个元素，它的效果非常好。然而，一旦我使用 4 个或更多元素，我就会失去一些排列。仅查看 4 的输出，我就缺少 7 个排列。

#include <stdio.h>
#include <iostream>

using namespace std;


//ms = magic square
//n = size
void perm(int ms[], int n) {
    int pivot = 0;
    int index = 0;
    int pivBit = 1;
    int fin = 0;
    int hold = 0;

    //While we are not finished
    while (fin == 0)  {
        //Incriment the index
        ++index;
        if (index >= n) {
            index = 0;
        }
        //if index is equal to the pivot
        if (index == pivot) {
            //Is this the first time visiting the pivot?
            if (pivBit == 0) {
                //Are we at the beginning again?
                if (index == 0 && pivot == 0)
                {
                    fin = 1;
                }
                pivBit = 1;
                ++index;
            }
            //Second time visiting? 
            else {
                pivBit = 0;
                ++pivot;
                if (pivot >= n) {
                    pivot = 0;
                }
            }
        }

        //If we are out of bounds
        if (index >= n) {
            index = 0;
        }

        //swap
        hold = ms[index];
        ms[index] = ms[pivot];
        ms[pivot] = hold;

        for (int i = 0; i < n; ++i) {
            cout << ms[i];
            if (i < n - 1) {
                cout << ", ";
            }
            else {
                cout << endl;
            }


        }

    }

}



int main() {

    cout << "Are you ready to brute force, my brother?" << endl;

    //Set
    int magicsquare[] = { 1, 2, 3, 4};
    int size = 4;

    perm(magicsquare, size);

    getchar();
    return 0;
}

我的输出是:

2 1 3 4
3 1 2 4
4 1 2 3
1 4 2 3
1 2 4 3
1 3 4 2
3 1 4 2 
3 4 1 2
3 4 2 1
2 4 3 1
2 3 4 1 
2 3 1 4
4 3 1 2
4 2 1 3
4 2 3 1
1 2 3 4
2 1 3 4

看着它，我已经可以看到我同时缺少 1 4 3 2 和 1 3 2 4。我的算法哪里出错了？

Answer 1

关于排列的 wiki 文章包括一个通用算法，用于按字典顺序生成所有排列，从顺序递增的整数数组开始，以反转的数组结束。 wiki next permutation .

如果处理一个对象数组，您可以生成一个索引 0 到 n-1 的数组，然后对索引使用下一个排列来生成对象数组的所有排列。

您还可以在网络上搜索下一个排列以找到类似的算法。递归的产生所有排列，但不是按字典顺序排列。