不带 inversions/reversions 的字典顺序字符串排列

Question

问题：

我想生成一个字符串排列的列表，但不包括字符串反转。例如，如果我有以下字符串：abc，我想生成以下列表

abc
acb
bac

而不是典型的

abc
acb
bac
bca
cab
cba

另一个例子看起来像这样：

100
010

而不是

100
010 
001

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

我曾想过应用如下内容：

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

然后比较，如果primed list值与原始值匹配，则保留原位，如果不同，如果其索引大于中值索引，则保留，否则删除。

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

任何建议都很好。

Answer 1

建议重复 Generating permutations which are not mirrors of each other 中的答案不处理重复的元素（因为那不是该问题的一部分）所以天真地遵循它会包括例如0100 和 0010。所以这不是完全相同的。但这个想法适用。

生成所有排列，但仅过滤具有 $_ le reverse $_ 的排列。我认为这基本上就是您在问题中提出的建议，但是当应用于每个排列的简单表达式将告诉您是否包含它时，无需计算映射。

Answer 2

示例代表的两种可能性是所有元素都不同的排列 (abcd)，或者两个符号的变体，其中一个符号只出现一次 (1000)。还解决了更一般的情况。

Non-repeating个元素（排列）

在这里我们可以利用 Algorithm::Permute 和特定的观察结果： 需要排除第一个元素大于最后一个元素的每个排列。它来自 this post, brought up in the .

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

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) 可以用与上述完全相同的方式处理，我们还需要修剪重复项作为 [=17= 的排列] 生成 abbcd 和 abbcd （相同）

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

在构建过程中这样做既不会降低复杂性也不会加快速度。

permute 被引用为模块中迄今为止最快的方法。它比我测试的其他模块（下面）快一个数量级，在我的系统上 10 个元素大约需要 1 秒。但请注意，此问题的复杂度为阶乘。炸得真快。

两个符号，其中一个只出现一次（变体）

这是不同的，上面的模块不适合它，排除标准也不起作用。还有其他模块，见文末。不过，这里的问题很简单。

从列表中的 (1,0,0,...) 和 'walk' 1 开始，直到 "midpoint" – 这是偶数列表的一半（4 表示 8 长), 或奇数尺寸的下半场（9 长为 5）。这样得到的所有字符串，通过将 1 移动一个位置到中点，形成集合。第二个 "half" 是它们的倒置。

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;

我们需要在最后一个索引之前停止，因为它已在上一次迭代中被填充。

如果两个符号 (0,1) 可能重复出现，这可以修改，但使用模块然后排除逆向要简单得多。 Algorithm::Combinatorics 这里有满足所有需求的例程。对于长度 $size 的 0 和 1 的所有变体，其中两者可能重复

use Algorithm::Combinatorics qw(variations_with_repetition);

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

然后可以通过 brute-force 搜索排除逆向元素，最坏情况下具有 O(N²) 复杂度。

另请注意 Math::Combinatorics。

不带 inversions/reversions 的字典顺序字符串排列

String permutations in lexigraphic order without inversions/reversions

string

algorithm

perl

permutation

combinatorics