我在创建一个将置换作为输入并打印出独立循环（以循环符号表示）的函数时遇到了问题。我将不胜感激。
输入：
1 2 3 4 5 6
5 3 2 6 4 1
输出：
(1 5 4 6)(2 3)
以第一个数字（数字）开头，按照映射进行操作，直到返回第一个数字。这是您的第一个周期。
然后从尚未访问的下一个号码开始，然后重复该过程。
重复直到访问完所有号码。
↓ Start at first number
1 2 3 4 5 6 1
5 3 2 6 4 1
* ↓ 1 maps to 5:
1 2 3 4 5 6 1 → 5
5 3 2 6 4 1
* ↓ * 5 maps to 4:
1 2 3 4 5 6 1 → 5 → 4
5 3 2 6 4 1
* * * ↓ 4 maps to 6:
1 2 3 4 5 6 1 → 5 → 4 → 6
5 3 2 6 4 1
* * * * 6 maps to 1:
1 2 3 4 5 6 1 → 5 → 4 → 6 → 1
5 3 2 6 4 1 First cycle complete
* ↓ * * * Start at first unvisited number:
1 2 3 4 5 6 2
5 3 2 6 4 1
* * ↓ * * * 2 maps to 3:
1 2 3 4 5 6 2 → 3
5 3 2 6 4 1
* * * * * * 3 maps to 2:
1 2 3 4 5 6 2 → 3 → 2
5 3 2 6 4 1 Second cycle complete
All digits visited, result:
1 → 5 → 4 → 6 and 2 → 3 ⇒ (1546)(23)
现在，您只需使用自己喜欢的任何一种语言编写代码。
提示：您将需要3个数组，一个用于第一组数字，一个用于第二组数字，以及一个用于跟踪访问过哪些数字的数组。
[您还需要一些东西来捕获结果，例如如果使用Java，则为StringBuilder。
UPDATE
这里是一个支持负数和多位数的Java解决方案，并具有完整的输入验证：
private static String findCycles(int[] a, int[] b) {
if (a.length == 0)
throw new IllegalArgumentException("The sets cannot be empty");
if (a.length != b.length)
throw new IllegalArgumentException("Sets must have same size: " + a.length + " != " + b.length);
TreeMap<Integer, Integer> numIdx = IntStream.range(0, a.length).boxed()
.collect(Collectors.toMap(i -> a[i], Function.identity(),
(i1, i2) -> { throw new IllegalArgumentException("Duplicate numbers not allowed: " + a[i1]); },
TreeMap::new));
if (! IntStream.of(b).boxed().collect(Collectors.toSet()).equals(numIdx.keySet()))
throw new IllegalArgumentException("Sets must consist of the same numbers");
String separator = (numIdx.firstKey() < 0 || numIdx.lastKey() > 9 ? " " : "");
BitSet used = new BitSet(a.length);
StringBuilder result = new StringBuilder();
for (int idx; (idx = used.nextClearBit(0)) < a.length; ) {
StringJoiner cycle = new StringJoiner(separator, "(", ")");
do {
used.set(idx);
cycle.add(String.valueOf(a[idx]));
idx = numIdx.get(b[idx]);
} while (! used.get(idx));
result.append(cycle.toString());
}
return result.toString();
}
Test
// Example from question:
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6 },
new int[] { 5, 3, 2, 6, 4, 1 }));
// Examples from https://en.wikipedia.org/wiki/Cyclic_permutation:
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 },
new int[] { 4, 2, 7, 6, 5, 8, 1, 3 }));
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 },
new int[] { 4, 5, 7, 6, 8, 2, 1, 3 }));
System.out.println(findCycles(new int[] { 1, 2, 3, 4 },
new int[] { 1, 4, 3, 2 }));
// Support for negative and multi-digit values:
System.out.println(findCycles(new int[] { -5, 0, 5, 10 },
new int[] { 0, 5, -5, 10 }));
输出
(1546)(23)
(146837)(2)(5)
(14625837)
(1)(24)(3)
(-5 0 5)(10)
我将向您展示（众多）之一可能的解决方案和一个完整的C ++工作示例。
我们只是沿着两个排列的路径前进。我们需要注意independent循环，防止出现两次循环，并且需要避免无限循环循环。
秘密是选择正确的容器类型。我使用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。在我们的自定义比较器中，我们将首先将这两个集合复制到std :: 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 = {
{1,2,3,4,5,6},
{5,3,2,6,4,1} };
// 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);
}
}
// Show result. 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;
}