按字母顺序排列的字符串排列，无反转/反转 [英] String permutations in lexigraphic order without inversions/reversions

问题描述

问题:

我想生成一个按字母顺序排列的字符串排列列表，但不包括字符串倒置.例如，如果我有以下字符串:abc，我想生成以下列表

I would like to generate a list of permutations of strings in lexigraphical but excluding string inversions. For instance, if I have the following string: abc, I would like to generate the following list

abc
acb
bac

代替典型的

abc
acb
bac
bca
cab
cba

另一个示例如下所示:

100
010

代替

100
010 
001

当前，我可以使用perl生成排列，但是我不确定如何最好地删除反向重复项.

Currently, I can generate the permutations using perl, but I am not sure on how to best remove the reverse duplicates.

我曾想过应用以下内容:

I had thought of applying something like the following:

create map with the following:
1)   100
2)   010
3)   001
then perform the reversion/inversion on each element in the map and create a new map with:

 1') 001
 2') 010
 3') 100

然后进行比较，如果有条件的列表值与原始值匹配，则将其保留在原位置；如果不同，则将其保留，否则将其删除.

then compare and if the primed list value matches the original value, leave it in place, if it is different, if it's index is greater than the median index, keep it, else remove.

问题是，我不确定这是否是一种有效的方法.

Trouble is, I am not sure if this is an efficient approach or not.

任何建议都会很棒.

推荐答案

示例所代表的两种可能性是，对于所有元素都不同的置换(abcd)，或者对于两个符号的变体，其中一个恰好出现一次().更一般的情况也得到解决.

Two possibilities represented by examples are for permutations where all elements are different (abcd), or for variations of two symbols where one appears exactly once (1000). More general cases are addressed as well.

非重复元素(排列)

在这里，我们可以使用 Algorithm :: Permute ，以及特定的观察结果: 需要排除第一个元素大于最后一个元素的每个排列.它来自此帖子，该帖子在由ysth回答.

Here we can make use of Algorithm::Permute, and of the particular observation: Each permutation where the first element is greater than its last need be excluded. It comes from this post, brought up in the answer by ysth.

该规则如下.考虑不带第一个和最后一个元素的字符串的子字符串.对于每个这样的子字符串，字符串的所有排列都必须包含其逆.因此，其中最后一个和第一个填充的其中一个是字符串的倒数.通过构造，对于每个子串，恰好有一个逆.因此，需要排除每个字符串的交换的第一个和最后一个元素的置换.

This rule holds as follows. Consider substrings of a string without its first and last elements. For each such substring, all permutations of the string must contain its inverse. One of these, padded with last and first, is thus the inverse of the string. By construction, for each substring there is exactly one inverse. Thus permutations with swapped first and last elements of each string need be excluded.

use warnings;
use strict;
use feature 'say';

use Algorithm::Permute;

my $size = shift || 4;
my @arr = ('a'..'z')[0..$size-1];  # 1..$size for numbers

my @res;    
Algorithm::Permute::permute { 
    push @res, (join '', @arr) unless $arr[0] gt $arr[-1] 
} @arr; 

say for @arr;

具有重复元素的问题 (abbcd)的处理方式与上述完全相同，并且我们还需要修剪重复项，因为b的排列会生成abbcd和abbcd (相同)

Problems with repetead elements (abbcd) can be treated the exact same way as above, and we need to also prune duplicates as permutations of b generate abbcd and abbcd (same)

use List::MoreUtils 'uniq';
# build @res the same way as above ...
my @res = uniq @res;

在施工过程中这样做不会降低复杂性，也不会加快工作速度.

Doing this during construction would not reduce complexity nor speed things up.

到目前为止，permute被引用为模块中最快的方法.它比我测试的其他模块(下图)快一个数量级，对我系统上的10个元素大约要花费1秒钟的时间.但是请注意，此问题的复杂性在大小上是 factorial .它炸得真快.

The permute is quoted as the fastest method in the module, by far. It is about an order of magnitude faster than the other modules I tested (below), taking about 1 second for 10 elements on my system. But note that this problem's complexity is factorial in size. It blows up really fast.

两个符号，其中一个恰好出现一次(变化)

这是不同的，上面的模块并不适用于此，排除标准也不起作用.还有其他模块，请参阅最后.但是，这里的问题非常简单.

This is different and the above module is not meant for it, nor would the exclusion criterion work. There are other modules, see at the end. However, the problem here is very simple.

从(1,0,0,...)开始，然后沿列表"walk" 1到达中点"–这是偶数大小列表的一半(8个长度为4)，或奇数大小的下一个过去一半(9个长度为5).通过将1向上移动一个位置直至中点，以这种方式获得的所有字符串形成集合.第二个一半"是它们的倒置.

Start from (1,0,0,...) and 'walk' 1 along the list, up to the "midpoint" – which is the half for even sized list (4 for 8-long), or next past half for odd sizes (5 for 9-long). All strings obtained this way, by moving 1 by one position up to midpoint, form the set. The second "half" are their inversions.

use warnings;
use strict;

my $size = shift || 4;
my @n = (1, map { 0 } 1..$size-1);   

my @res = (join '', @n);       # first element of the result

my $end_idx = ( @n % 2 == 0 ) ? @n/2 - 1 : int(@n/2);

foreach my $i (0..$end_idx-1)  # stop one short as we write one past $i
{
    @n[$i, $i+1] = (0, 1);     # move 1 by one position from where it is
    push @res, join '', @n;
}

print "$_\n" for @res;

由于上一次迭代中已填充了最后一个索引，因此我们需要在最后一个索引之前停止.

We need to stop before the last index since it has been filled in the previous iteration.

如果两个符号(0,1)可能反复出现，可以对此进行修改，但是使用模块然后排除反函数要简单得多. Algorithm :: Combinatorics 在此处具有满足所有需求的例程.对于长度$size的0和1的所有变体，两者都可能重复

This can be modified if both symbols (0,1) may appear repeatedly, but it is far simpler to use a module and then exclude inverses. The Algorithm::Combinatorics has routines for all needs here. For all variations of 0 and 1 of lenght $size, where both may repeat

use Algorithm::Combinatorics qw(variations_with_repetition);

my @rep_vars = variations_with_repetition([0, 1], $size);

然后，可以用蛮力搜索排除

逆元素，最复杂的情​​况是 O(N ² ).

Inverse elements can then be excluded by a brute-force search, with O(N²) complexity at worst.

还请注意 Math :: Combinatorics .

这篇关于按字母顺序排列的字符串排列，无反转/反转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！