相互置換算法

Question

我有一組元素，說

A1，B1，B2。

這裏，a和b分別屬於兩類元素。我想要一個算法列出這兩個類之間的所有安排。例如，

{a1 b1}，{a1 b2}，{b1 a1}，{b2 a1}。

注意，

1）應避免在同一類元素之中的安排，

2）的類的數量可以大於2，和

3）屬於不同類別的元素數量可能不相同。

提前致謝！

Answer 1

如果你不是過分關注效率，你可以這樣做（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)); 
    } 
} 

Answer 2

對於情況，其中k = 2（類號碼）：

1）第一元素從K1匹配的每個元素在K2

2）爲每個這樣的匹配創建所有排列

3）的所有排列加入到最終的列表

4）繼續與K1

其餘元件

對於k> 2的情況，您需要擴展它，以便首先從K1中取出第一個元素，K2中的第一個元素，然後剩下的K3（或者先在K3中繼續，然後繼續K4，..，Kn）。

Answer 3

你可以使用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')]