2楼 迭代算法分析 - Fischer-Krause ordered permutation 转 C 代码,以及解释
[4楼]递归+元素调换 —— 最直接的算法
[5楼]耳目一新的迭代法 —— 通过进制转换原理计算模式,再应用到排列
[算法]Permutation - 元素排列
- 523066680
- Administrator
- 帖子: 335
- 注册时间: 2016年07月19日 12:14
- 拥有现金: 锁定
- 储蓄: 锁定
- Has thanked: 29 times
- Been thanked: 23 times
- 联系:
Fischer-Krause ordered permutation 转 C 代码,以及解释
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:
来自 perldoc -q permute, 调用示例:echo a b c | permute.pl
解读和代码转C,主要是有一个数字调换的规律
有了这一个规则,我们可以 通过某个中间的排列得出下一个结果:
举一个 6 位的
arr[] = 5 3 4 2 1 0
等有时间就做个图什么的... 未完待续
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], 得
等有时间就做个图什么的... 未完待续
- 523066680
- Administrator
- 帖子: 335
- 注册时间: 2016年07月19日 12:14
- 拥有现金: 锁定
- 储蓄: 锁定
- Has thanked: 29 times
- Been thanked: 23 times
- 联系:
[算法]Permutation - 元素排列,递归方案
另一段 Perl 排列元素的代码 看上去相当简练,不过应该还是递归提取和堆叠元素的思路,只是语法糖用的比较到位。
Permutations using 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
- 帖子: 335
- 注册时间: 2016年07月19日 12:14
- 拥有现金: 锁定
- 储蓄: 锁定
- Has thanked: 29 times
- Been thanked: 23 times
- 联系:
C,递归,目前看到的最直接也最简练的算法
这段代码引自: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
- 帖子: 335
- 注册时间: 2016年07月19日 12:14
- 拥有现金: 锁定
- 储蓄: 锁定
- Has thanked: 29 times
- Been thanked: 23 times
- 联系:
耳目一新的迭代法 —— 通过进制转换原理计算模式,再应用到排列
编辑/整理:523066680@163.com
日期:2017-05
转载请注明出处:http://www.code-by.org/viewtopic.php?f=29&t=261
序
日期: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;
- }
在线用户
用户浏览此论坛: 没有注册用户 和 1 访客