[算法]Permutation - 元素排列

回复
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

[算法]Permutation - 元素排列

帖子 523066680 »

头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Fischer-Krause ordered permutation 转 C 代码,以及解释

帖子 523066680 »

Fischer-Krause ordered

Here's a little program that generates all permutations of all the words
on each line of input. The algorithm embodied in the "permute()"
function is discussed in Volume 4 (still unpublished) of Knuth's *The
Art of Computer Programming* and will work on any list:

#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
my $code = shift;
my @idx = 0..$#_;
while ( $code->(@_[@idx]) ) {
my $p = $#idx;
--$p while $idx[$p-1] > $idx[$p];
my $q = $p or return;
push @idx, reverse splice @idx, $p;
++$q while $idx[$p-1] > $idx[$q];
@idx[$p-1,$q]=@idx[$q,$p-1];
}
}

permute { print "@_\n" } split;
来自 perldoc -q permute, 调用示例:echo a b c | permute.pl

解读和代码转C,主要是有一个数字调换的规律
/* Translate by 523066680@163.com */
#include <stdio.h>

void splice_and_reverse( int *arr, int p, int ubound )
{
int t;
for (int i = p; i <= (ubound+p)/2 ; i++ )
{
t = arr[i];
arr[i] = arr[ubound - i + p];
arr[ubound - i + p] = t;
}
}

void exchange(int *arr, int a, int b)
{
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}

void print_array(int *arr, int ubound)
{
for (int i = 0; i <= ubound; i++)
printf("%d", arr[i]);

printf("\n");
}

int main(int argc, char *argv[] )
{
int arr[] = {0, 1, 2, 3};
int ubound = sizeof(arr) / sizeof(arr[0]) - 1;
int p, q;

while (1)
{
p = ubound;

//p 递减,直到 当前元素 > 上一个元素 ,上一个元素记为 N
while ( arr[p-1] > arr[p] ) p--;

if ( p <= 0 ) break;

q = p;

//反转 从 p 至 末尾的元素
splice_and_reverse( arr, p, ubound );

//q 递增,直到当前元素 > N
while ( arr[p-1] > arr[q] ) q++;

//交换
exchange(arr, p-1, q);

//打印结果
print_array(arr, ubound);
}

return 0;
}
有了这一个规则,我们可以 通过某个中间的排列得出下一个结果:

举一个 6 位的
arr[] = 5 3 4 2 1 0
  • 从右往左寻找 前一项小于当前项 的情况(3和4), 下标 p = 2; 记住前一项 = 3
  • 反转以 p 为起点,至末尾的项, arr[] = 5 3 0 1 2 4
  • 之后的计算依据 5 3 0 1 2 4
  • 以 arr[2] 为起点,向右寻找 > 3 的项的下标, 4 > 3, 所以 q = 5;
    从 5 3 0 1 2 4 调换 arr[p-1], arr[q], 得
arr[] = 5 4 0 1 2 3

等有时间就做个图什么的... 未完待续
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

[算法]Permutation - 元素排列,递归方案

帖子 523066680 »

另一段 Perl 排列元素的代码 看上去相当简练,不过应该还是递归提取和堆叠元素的思路,只是语法糖用的比较到位。

Permutations using Perl
steabert - There is a nice lecture on YouTube in the Stanford programming paradigms series about doing permutation with recursion and double mapping in Scheme. In Perl, I came up with the following implementation for the algorithm:
#!/usr/bin/perl
use strict;
use warnings;

my @array = qw(a b c);

sub permute {
return ([]) unless (@_);
return map {
my @cdr = @_;
my $car = splice @cdr, $_, 1;
map { [$car, @$_]; } &permute(@cdr);
} 0 .. $#_;
}

print "@$_\n" foreach (&permute (@array));
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

C,递归,目前看到的最直接也最简练的算法

帖子 523066680 »

这段代码引自:http://bbs.bathome.net/thread-43749-1-1.html
#include <stdio.h>
#include <string.h>

void swap(char *a, char *b)
{
char tmp = *a;
*a = *b;
*b = tmp;
}

void arrange(char *str, int start, int end)
{
int i;
if(start == end)
{
printf("%s\n",str);

}else{
for(i = start; i < end; i++)
{
swap(str+start,str+i);
arrange(str,start+1,end);
swap(str+start,str+i);
}

}
}

int main(void)
{
char str[10]="bathome";
int len = strlen(str);
arrange(str,0,len);
return 0;
}
和常规的递归思路一样,层层提取,但是把递归结构应用到极致,没有多余的副本创建,整个代码展现出一种概念:
  • 数据 即 结构,结构 即 数据。
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

耳目一新的迭代法 —— 通过进制转换原理计算模式,再应用到排列

帖子 523066680 »

编辑/整理:523066680@163.com
日期:2017-05
转载请注明出处:http://www.code-by.org/viewtopic.php?f=29&t=261

  • 通过迭代方式获得排列的方案,参考自《Higher-Order Perl》
概念
  • 假设有4个元素: @arr = (a, b, c, d),下标为 0 1 2 3,每提取一个元素,
    数组重新定义,下标从0开始。排列和下标的提取关系:
    a b c d -> 0 0 0 0
    a b d b -> 0 0 1 0
    a c b d -> 0 1 0 0
    a c d b -> 0 1 1 0
    a d b c -> 0 2 0 0
    ...

    注意这里数字的变化和进制换算、递增非常相似,区别在于,每一位的进制是不同的:
    末位始终为0,
    倒数第二位最大为1(0,1),
    倒数第三位最大为2(0,1,2),
    倒数第四位最大为3(0,1,2,3)
    一共能产生 4×3×2×1 种模式(pattern) (刚好对应24种排列情况)
不同模式的生成和换算
  • 先设计一种换算函数,对于传入的任意数字,计算出对应的模式:
    my @elements = qw/a b c d/;   #元素
    my $seats = $#elements + 1; #数量
    my @order = (0) x $seats; #初始模板

    to_pattern(5, $seats, \@order);
    print join(",", @order);

    sub to_pattern #转换器
    {
    my ($num, $seats, $o_ref) = @_;
    my $mod;

    for my $div ( 1 .. $seats )
    {
    $mod = $num % $div;
    $num = int($num / $div);
    $o_ref->[-$div] = $mod; #倒序填入
    }
    }
    输出: 0,2,1,0
将模式应用到排列顺序
  • 再写一个函数将 模式应用于顺序地提取数组元素
    my @elements = qw/a b c d/;
    my $seats = $#elements + 1;
    my @order = (0, 2, 1, 0);

    apply(\@elements, \@order);

    sub apply
    {
    my ($e_ref, $o_ref) = @_;
    my @temp = @$e_ref;
    my @final;

    for my $idx ( @$o_ref )
    {
    push @final, splice( @temp, $idx, 1 );
    }

    print join(",", @final),"\n";
    }
    输出:a,d,c,b

    这样,不管想要哪一个序列,只要通过类似进制换算的方法算出模式,按模式提取即可
枚举所有情况的代码:
  • use strict;
    my @elements = qw/a b c d e/;
    my $seats = $#elements + 1;
    my @order = (0) x $seats;

    for my $n ( 0 .. factorial($seats)-1 )
    {
    my @result;
    to_pattern($n, $seats, \@order);
    apply( \@elements, \@order, \@result );
    print join(",", @result), "\n";
    }

    sub to_pattern
    {
    my ($n, $seats, $o_ref ) = @_;
    my $mod;

    for my $div ( 1 .. $seats )
    {
    $mod = $n % $div;
    $n = int($n / $div);
    $o_ref->[-$div] = $mod; #从右边向左填入
    }
    }

    sub apply
    {
    my ($e_ref, $o_ref, $result) = @_;
    my @temp = @$e_ref;

    for my $idx ( @$o_ref )
    {
    push @$result, splice( @temp, $idx, 1 );
    }
    }

    sub factorial
    {
    my $v = shift;
    return ($v > 1) ? $v*factorial($v-1) : 1;
    }
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [算法]Permutation - 元素排列

帖子 rubyish »

laige perl ~~ :lol:
#!/usr/bin/perl
# version 26, subversion 1 (v5.26.1)

use 5.010;


#my @data = grep chomp, <DATA>;
my @data = 'A' .. 'I';

#perm( \@data, 4 );

perm( \@data, ~~@data );

# ____________________SUB____________________
sub perm {
my ( $data, $numba ) = @_;
my @indes = 0 .. $numba - 1;
my @use = (0) x $numba;
@use[@indes] = (1) x @indes;

my $new = 1;
while ($new) {
say @{$data}[@indes];
$new = 0;

for ( my $poz = $#indes ; $poz >= 0 ; $poz-- ) {
$use[ $indes[$poz] ] = 0;

for my $it ( $indes[$poz] + 1 .. $#use ) {
$new = $it, last if !$use[$it];
}

next if !$new;

$use[$new] = 1;
$indes[$poz] = $new;
my $next = 0;
for my $p ( $poz + 1 .. $#indes ) {
for my $it ( $next .. $#use ) {
if ( not $use[$it] ) {
$use[$it] = 1;
$indes[$p] = $it;
$next = $it + 1;
last;
}
}
}

last;
}
}
}

__DATA__
$_
$_
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [算法]Permutation - 元素排列

帖子 523066680 »

rubyish 写了:laige perl ~~ :lol:
#!/usr/bin/perl
# version 26, subversion 1 (v5.26.1)
我就想起来你在 CU 的蜜汁代码

代码: 全选

E_( [ 1 .. 9 ], [] );

sub E_
{
    my ( $a, $b ) = @_;
    #此处省略若干代码
    E_( [ @$a[ 0 .. $_ - 1, $_ + 1 .. $#$a ] ], [ @$b, $a->[$_] ] )
        for 0 .. $#$a;
}
当时我还做了图,
图解递归排列元素.png
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [算法]Permutation - 元素排列

帖子 rubyish »

那個圖。真是 very very good。

$_
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [算法]Permutation - 元素排列

帖子 rubyish »

我想。如果他反覆。一再反覆。閱讀。
必定會得到啟發。

$_
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 1 访客