互置换算法

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

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

Answer 3

对于k=2(类数)的情况：

1)将K1中的第一个元素与K2中的每个元素匹配

2)为每一次这样的匹配创建所有排列

3)将所有排列添加到最终列表中

4)继续使用K1中的剩余元素

对于k>2的情况，您需要扩展这一点，以便您首先从K1中获取第一个元素，在K2中获取第一个元素，然后在K3中获取剩下的元素(或者在K3中首先使用K4，.，Kn)。