[算法]Permutation - 元素排列

[523066680]

2楼 迭代算法分析 - Fischer-Krause ordered permutation 转 C 代码，以及解释
[4楼]递归+元素调换 —— 最直接的算法
[5楼]耳目一新的迭代法 —— 通过进制转换原理计算模式，再应用到排列

[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:

Code: [show] | [select all]

#!/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，主要是有一个数字调换的规律

Code: [show] | [select all]

/* 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]

另一段 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:

Code: [show] | [select all]

#!/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]

这段代码引自：http://bbs.bathome.net/thread-43749-1-1.html

Code: [show] | [select all]

#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]

编辑/整理：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种排列情况）

不同模式的生成和换算

• 先设计一种换算函数，对于传入的任意数字，计算出对应的模式：
  Code: [show] | [select all]

  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

将模式应用到排列顺序

• 再写一个函数将 模式应用于顺序地提取数组元素
  Code: [show] | [select all]

  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
  
  这样，不管想要哪一个序列，只要通过类似进制换算的方法算出模式，按模式提取即可

枚举所有情况的代码：

• Code: [show] | [select all]

  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]

laige perl ~~

Code: [show] | [select all]

#!/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]

laige perl ~~

Code: [show] | [select all]

#!/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]

那個圖。真是 very very good。

[rubyish]

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