数学/算法从来都不是我的强项(!)所以在这方面请求帮助。
对于具有以下签名的方法，什么是最有效的实现:
/*
* pairParts.size() > 0
* pairParts.size() is always an even number
*/
private Set<StringPairGroup> getAllPossibleStringPairGroups(Set<String> pairParts) {
Set<StringPairGroup> groups = new HashSet<StringPairGroup>();
// logic that adds all possible StringPairGroups
` return groups;
}
/*
* StringPair object: first and second values cannot be null.
* StringPair object: first != second
* StringPair object: is equal to another if both the first values and both the second values are equal.
*/
public class StringPair {
private final String first;
private final String second;
...
}
/*
* StringPairGroup object: is equal to another if their StringPair sets exactly match.
*/
public class StringPairGroup {
Set<StringPair> stringPairs
...
}
作为一个例子，输入{'A'， 'B'}将返回{[AB]，[BA]}。将返回{'A'， 'B'， 'C'， 'D'}的输入{(AB), (BA), (AC), (CA),[广告],(DA)[…]、[AB、CD], [BA、CD], [AB特区],[英航特区]、[AC, DB ],[...]}.
我真的只是对创建所有可能的StringPairGroups的逻辑感兴趣用于任何一组输入字符串。我可能会想出一些蛮力实现，但我宁愿知道如何做一些更"聪明"的事情。
所以任何关于我如何实现它的提示都会很有用。
编辑:对不起，伙计们，我想我可能错过了一些非常重要的事情。我真的开始困惑了。StringPairGroup不能在其所有stringpair中包含重复的"pair部分"。明白了吗?
我会这样做:
- 在StringPair中实现一个比较，当传入另一个StringPair时比较它们是否共享任何元素:boolean shareElement(StringPair other)
- 我可以创建所有可能的StringPairs [AB]， [BA]， [AC]， [CA]的列表
-
我将对 I = 1 - (originalList.size()/2)…
。从唯一对列表中创建i个元素的组合，这些元素不共享任何元素
将这个解决方案与@Hemal Pandya的解决方案结合起来，我想你会得到答案的。也就是说，将Hemal的集合递归组合与上面的shareElement结合使用。
编辑:我也会创建一个布尔shareElement(StringPair…
我对问题的理解如下。有一个N个不同字符串的集合(N是偶数)例:A, B, C, D。pair是此集合中两个不同字符串的任意连接。AB BA是对的，但AA不是对的。一双和另一双是不同的如果对应的连接字符串是不同的字符串。所以AB不同于BA，AB等于AB(很明显)有N*N - N种不同的对可以构建N个不同的字符串
k阶的群是k对的集合。所以[AB] [CD]是1阶的群因为它们都有一对。[AB, CD]， [BA, CD]是2阶的群，因为它们都包含2对。两组相等当且仅当它们相等为两个集合。所以，两个相等基团有完全相同的对;配对的顺序无关紧要。例如,[AB, CD]和[BA, CD]是不同的基团，因为不是它们中的所有对都相等。[AB, CD]和[CD, AB]是两个相等的组。
所有k阶的群都可以递归构造:
- 选择任意P对字符串
- 如果k = 1，则返回从所有这些对构建的组
- 如果k> 1:
3.1将这对从N个字符串的集合C(N)中移除，留下一个集合C(N-2)剩下的字符串。
3.2从C(N-2)中构造k-1阶的所有组，并与p对组合。
这是一个Java程序(完整的代码在github:gist)。一个可执行程序在ideone.
public static class Pair {
public String s1, s2;
public Pair(String s1, String s2) {
this.s1 = s1; this.s2 = s2;
}
public String toString() {
return s1 + s2;
}
}
public static class Group {
public List<Pair> pairs = new ArrayList<Pair>();
public Group(Pair p) {pairs.add(p);}
}
public static List<Group> getGroups(String[] strings, int order) {
List<Group> groups = new ArrayList<Group>();
for (int i = 0; i < strings.length; ++i) {
for (int j = 0; j < strings.length; ++j) {
if (i != j) {
Pair p = new Pair(strings[i], strings[j]);
if (order == 1) {
groups.add(new Group(p));
}
else {
String[] strings2 = new String[strings.length - 2];
for (int k = 0, k2 = 0; k < strings.length; ++k) {
if (k != i && k != j) {
strings2[k2++] = strings[k];
}
}
List<Group> groups2 = getGroups(strings2, order - 1);
for (int k = 0; k < groups2.size(); ++k) {
Group g = new Group(p);
groups.add(g);
Group g2 = groups2.get(k);
g.pairs.addAll(g2.pairs);
}
}
}
}
}
return groups;
}
有N/2种可能的顺序。为所有这些订单构造组并附加它们。
String strings[] = {"A", "B", "C", "D", "E", "F"};
List<Group> groups = new ArrayList<Group>();
for (int order = 1; order <= strings.length/2; ++order) {
List<Group> groups2 = getGroups(strings, order);
groups.addAll(groups2);
}
递归解决方案很容易理解，但效率较低。如果N很大那么你就需要一个更快的迭代解决方案。迭代解更少比递归的更能说明问题，不适合这里的演示。你可以参考Knuth:计算机程序设计的艺术，卷4A:组合算法。
我不知道这是否有效，但这里有一个尝试。
在步骤1中给定A, B, C生成[A,B], [A,C], [B, A], [B, C], [C, A], [C, B]
这很容易(对吗?)。
现在，一开始你有一个包含3个元素的集合，每个元素的大小为1，从中你生成了元素对。
在第一步之后，你有6个元素的集合，每个元素的大小为2，所以你做与第一步相同的事情来生成二阶集合。
以此类推，直到有一个元素的集合
有意义吗?
看你的笔记，顺序不重要，我想这可能是不正确的。
我会分两个阶段来做。首先，我要创建一个Iterable实现，它有一个构造函数，可以接受Set作为参数。
然后将Set转换为数组(我使用Set而不是任何其他集合来保证输入集合的唯一性)。如果你能保证没有并发访问，你就不需要把它存储到数组中。
然后根据数组的大小计算可能排列的数量，并将其存储到final变量中。公式应该是N!/2我认为。
然后创建两个索引(或迭代器)。第一个p在第一个元素上第二个q在第二个元素上每次调用iterate时，我会检查q是否在末尾，如果是，将q重置为第一个元素，并将p增加1。如果p也在末尾，则表示没有更多的元素。否则返回p和q的新字符串对。
然后我可以使用这个可迭代对象来创建一个新的字符串对集合、数组等。
分隔将允许您节省内存，因为除非您需要，否则您不会存储字符串对组。