生成不同订单的算法

Question

我正在尝试编写一个生成不同集合的简单算法

(cba)(cab)(bac)(bca)(acb)from(abc)

做两个操作:

交换输入的第一和第二元素(abc),所以我得到(bac)

然后将第一个元素移到最后=>输入是(bac),输出是(acb)

所以这个程序的最终输出是(acb).

当然,这种方法只生成acb和ab c.我想知道是否使用这两个操作(可能连续使用2个交换然后换班,或任何变化)足以产生所有不同的排序？

我想提出一个简单的算法,不使用> <或+,只需重复交换某些位置(例如总是交换位置1和2)并始终移动某些位置(例如将第一个元素移动到最后一个).

Answer 1

请注意,移位操作(将第一个元素移动到结尾)相当于允许任何相邻对的交换(交换):您只需移动直到到达要交换的对,然后交换元素.

因此,您的问题基本上等同于以下问题:是否可以仅使用相邻对交换生成每个排列.如果是的话,是否有算法可以做到这一点.

答案是肯定的(两个问题).其中一种算法叫做"Johnson-Trotter算法",你可以在维基百科上找到它.