Heap 的排列生成算法生成重复结果

Question

我正在使用堆的算法来生成列表的所有排列，但由于某种原因我的实现不起作用。具体来说，它产生了正确数量的排列 n!，但它丢失了一些排列，并用先前排列的副本填充了空白。以下是它用 3 种物品生产的产品： （重复项的第一个实例用 f 标记，第二个实例用 s 标记，第三个实例用 t 标记，标记是我完成的，而不是代码）

0, 1, 2,
1, 0, 2,
2, 1, 0, f
1, 2, 0, f
2, 1, 0, s
1, 2, 0, s

这是它用四种物品生产的：

0, 1, 2, 3,
1, 0, 2, 3,
2, 1, 0, 3, f
1, 2, 0, 3, f
2, 1, 0, 3, s
1, 2, 0, 3, s
3, 1, 2, 0,
1, 3, 2, 0, f
2, 1, 3, 0,
1, 2, 3, 0, f
0, 1, 3, 2,
1, 0, 3, 2,
1, 3, 2, 0, s
0, 3, 2, 1,
2, 3, 1, 0, f
0, 3, 1, 2, f
3, 2, 1, 0, f
1, 2, 3, 0, s
2, 3, 1, 0, s
0, 3, 1, 2, s
3, 2, 1, 0, s
1, 2, 3, 0, t
2, 3, 1, 0, t
0, 3, 1, 2, t

这是我的代码：

vector<vector<int>> permutations;

void GenerateAllPermutations(vector<int> v, int size)
{
    // if size becomes 1 then adds on the obtained permutation
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);

        // if size is odd, swap first and last element
        if (size % 2 == 1)
        {
            iter_swap(v.begin(), v.begin() + v[size - 1]);
        }
        // If size is even, swap ith and last element
        else
        {
            iter_swap(v.begin() + i, v.begin() + v[size - 1]);
        }
    }
}

int main()
{
    vector<int> v = { 0, 1, 2, 3 };
    GenerateAllPermutations(v, v.size());
    // prints all the generated permutations
    for (int i = 0; i < permutations.size(); i++)
    {
        for (int x = 0; x < permutations[i].size(); x++)
        {
            cout << permutations[i][x] << ", ";
        }
        cout << endl;
    }
}

Answer 1

您的代码中有两个错误：

1. v.begin() + v[size - 1]

   没有任何意义：

   v[size - 1]

   不是偏移量，而是数据值。这个应该是

   v.begin() + size - 1

2. 堆算法的递归版本旨在让每个递归操作same数组，但向量是按值传递的，并且由于它们不是指针，因此该向量的突变只会发生在该执行上下文中，而不是发生在呼叫者的向量。另请参阅 C++ 中向量是按值还是按引用传递给函数 和 通过值的引用传递向量不会在传递的原始向量中发生变化？

通过这些更正，它将起作用：

// pass vector by reference
void GenerateAllPermutations(std::vector<int> &v, int size)
{
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);
        if (size % 2 == 1)
        {
            // Don't pass a data value, but an offset
            iter_swap(v.begin(), v.begin() + size - 1);
        }
        else
        {
            iter_swap(v.begin() + i, v.begin() + size - 1);
        }
    }
}

虽然现在可以工作，但它执行的交换次数超出了必要的次数。请参阅维基百科关于频繁错误实现的部分，其中讨论了您的算法版本：

此实现将成功产生所有排列，但不会最小化移动。当递归调用堆栈展开时，它会导致每个级别都有额外的交换。其中一半将是无操作的 𝐴[𝑖] 和 𝐴[𝑘−1]，其中 𝑖==𝑘−1，但当 𝑘 为奇数时，会导致 𝑘^th 与第 0^th 元素进行额外交换。