c++ - 如何在 C++ 中的二维数组中进行置换循环？

Question

置换的循环是按顺序相互替换的元素的子集，直到最后一个元素被第一个元素替换。此时我得到了具有两行和“用户输入列”的动态二维数组，这些值也是从用户插入的。我需要从这个数组中进行排列循环。对不起，如果我做错了什么，这只是我第一次在这里发帖:)。我试过这个，但它不能正常工作：

    // First element in the array//
    int startingElement = arr[0][0];

    for (int i = 0; i < cols; i++) {

        // If first element in second row is not like the first element in first row we will print ‘(’ and also elements [0][0] and [1][0] //
        if (arr[0][i] != arr[1][i]) {
            cout << "(" << arr[0][i] << " " << arr[1][i];

            int positionOfSecondRowElementInFirstRow = 0;

            for (int firstRowElementIndex = 0; firstRowElementIndex < cols; firstRowElementIndex++) {

                // With this 'if' we will find in which colon(index) in first row we have the element from the second row //
                if (arr[0][firstRowElementIndex] == arr[1][i]) {
                    positionOfSecondRowElementInFirstRow = firstRowElementIndex;
                }
            }

            // This ‘if’ will check if element in first row is equal to out strating element. If it is the program will print ‘)’//
            if (arr[1][positionOfSecondRowElementInFirstRow] == startingElement) {
                cout << ")";

            }
        }

        // Else the program will print the element(this is working when we have fixed points)//
        else {
            cout << "(" << arr[0][i] << ")";
        }
    }

    return true;
} ```

标签： c++arrayspermutationcycle

Answer 1

不幸的是，我无法修复您给定的代码。这是相当错误的。我用调试器检查过，但没有成功。也是设计，算法似乎是错误的。

因此，我为您创建了一个全新的解决方案。

秘诀是选择正确的容器类型。我使用 2。对于循环，我使用std::unordered_set. 这只能包含唯一元素。这样，将防止无限循环。例如： 0,1,3,0,1,3,0,1,3 。. . 不可能，因为每个数字在容器中只能出现一次。这将阻止我们通过排列。一旦我们看到一个已经在循环中的数字，我们就会停下来。

所有找到的循环都将存储在第二种容器类型中： A std::set。std::set也可以只包含唯一值，并且这些值是有序的。因为我们在 中存储复杂的数据，所以std::set我们为它创建了一个自定义比较器。我们需要注意std::set不会包含 2 个重复条目。在我们的例子中，double 也是 0,1,3 和 1,3,0。在我们的自定义比较器中，我们首先将 2 个集合复制到 astd::vector中并对std::vectors 进行排序。这将使 1,3,0 变为 0,1,3。然后我们可以很容易地检测到双打。

请注意：

我总是只存储循环中第一个排列的值。第二个用作帮助器，以查找要评估的下一个值的索引。

请看下面的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <iterator>
#include <set>

// Make reading easier and define some alies names
using MyType = int;
using Cycle = std::unordered_set<MyType>;
using Permutation = std::vector<MyType>;
using Permutations = std::vector<Permutation>;

// We do not want to have double results. 
// A double cyle is also a Cycle with elements in different order
// So define custom comparator functor for our resulting set
struct Comparator {
    bool operator () (const Cycle& lhs, const Cycle& rhs) const {
        // Convert the unordered_sets to vectors
        std::vector<MyType> v1(lhs.begin(), lhs.end());
        std::vector<MyType> v2(rhs.begin(), rhs.end());
        // Sort them 
        std::sort(v1.begin(), v1.end());
        std::sort(v2.begin(), v2.end());
        // Compare them
        return v1 < v2;
    }
};
// Resulting cycles
using Cycles = std::set<Cycle, Comparator>;

int main() {

    // The source data
    Permutations perms2 = {
        {0,1,2,3,4,5,6,7,8},
        {1,3,7,0,4,8,2,6,5} };

    // Lamda to find the index of a given number in the first permutation
    auto findPos = [&perms2](const MyType& m) {return std::distance(perms2[0].begin(), std::find(perms2[0].begin(), perms2[0].end(), m)); };

    // Here we will store our resulting set of cycles
    Cycles resultingCycles{};

    // Go through all single elements of the first permutation
    for (size_t currentColumn = 0U; currentColumn < perms2[0].size(); ++currentColumn) {

        // This is a temporary for a cycle that we found in this loop
        Cycle trialCycle{};

        // First value to start with
        size_t startColumn = currentColumn;

        // Follow the complete path through the 2 permutations
        for (bool insertResult{ true }; insertResult; ) {

            // Insert found element from the first permutation in the current cycle
            const auto& [newElement, insertOk] = trialCycle.insert(perms2[0][startColumn]);
            // Find the index of the element under the first value (from the 2nd permutation)
            startColumn = findPos(perms2[1][startColumn]);
            // Check if we should continue (Could we inster a further element in our current cycle)
            insertResult = insertOk;
        }

        // We will only consider cycles with a length > 1
        if (trialCycle.size() > 1) {
            // Store the current temporary cycle as an additional result.
            resultingCycles.insert(trialCycle);
        }
    }


    // Simple output
    std::cout << "\n\nFound Cycles:\n\n";
    // Go through all found cycles
    for (const Cycle& c : resultingCycles) {
        // Print an opening brace
        std::cout << "(";
        // Handle the comma delimiter
        std::string delimiter{};

        // Print all integer values of the cycle
        for (const MyType& m : c) {
            std::cout << delimiter << m;
            delimiter = ",";
        }
        std::cout << ")";
    }
    std::cout << "\n\n";

    return 0;
}