我有一組元素,說相互置換算法
A1,B1,B2。
這裏,a和b分別屬於兩類元素。我想要一個算法列出這兩個類之間的所有安排。例如,
{a1 b1},{a1 b2},{b1 a1},{b2 a1}。
注意,
1)應避免在同一類元素之中的安排,
2)的類的數量可以大於2,和
3)屬於不同類別的元素數量可能不相同。
提前致謝!
我有一組元素,說相互置換算法
A1,B1,B2。
這裏,a和b分別屬於兩類元素。我想要一個算法列出這兩個類之間的所有安排。例如,
{a1 b1},{a1 b2},{b1 a1},{b2 a1}。
注意,
1)應避免在同一類元素之中的安排,
2)的類的數量可以大於2,和
3)屬於不同類別的元素數量可能不相同。
提前致謝!
如果你不是過分關注效率,你可以這樣做(Python)的
def mutualperms(lst, prefix=()):
if lst:
for x in lst:
yield from mutualperms([y for y in lst if not sameclass(x, y)],
prefix + (x,))
else:
yield prefix
(如果你不熟悉Python生成,認爲yield
爲print
而忽略yield from
)。
這是Java版本。
import java.util.*;
public class MutualPerms {
private static boolean sameClass(String arg1, String arg2) {
return arg1.charAt(0) == arg2.charAt(0);
}
private static void mutualPerms(Deque<String> prefix,
Collection<String> args) {
if (args.isEmpty()) {
for (String arg: prefix) {
System.out.print(arg);
System.out.print(' ');
}
System.out.println();
} else {
for (String arg1: args) {
prefix.addLast(arg1);
Collection<String> subargs = new ArrayList<String>();
for (String arg2: args) {
if (!sameClass(arg1, arg2)) {
subargs.add(arg2);
}
}
mutualPerms(prefix, subargs);
prefix.removeLast();
}
}
}
public static void main(String[] args) {
mutualPerms(new LinkedList<String>(), Arrays.asList(args));
}
}
對於情況,其中k = 2(類號碼):
1)第一元素從K1匹配的每個元素在K2
2)爲每個這樣的匹配創建所有排列
3)的所有排列加入到最終的列表
4)繼續與K1
其餘元件對於k> 2的情況,您需要擴展它,以便首先從K1中取出第一個元素,K2中的第一個元素,然後剩下的K3(或者先在K3中繼續,然後繼續K4,..,Kn)。
你可以使用Python的itertools.product做到這一點:
import itertools as itl
la = ['a1']
lb = ['b1', 'b2']
print list(itl.chain(itl.product(la, lb), itl.product(lb, la)))
輸出爲:
[('a1', 'b1'), ('a1', 'b2'), ('b1', 'a1'), ('b2', 'a1')]
值得注意它只能在Python3 – 2014-08-29 02:16:04
@DavidEisenstat,謝謝。你能否在「前綴」這個詞上多說一些?我不能完全遵循你的確切含義。 – user3167843 2014-09-02 03:42:17
@DavidEisenstat,謝謝。由於我對Python的知識非常少見,我不能完全遵循'prefix'和'(x,)'的用法。您能否通過好心地展示更多代碼或僞代碼來闡述如何實現這兩個術語? – user3167843 2014-09-02 04:04:01