求php算法，任意多个数字唯一性全排序算法

0 0

求php算法，任意多个数字唯一性全排序算法

这个应该要用递归来实现了，要求是这样的
$data = array('0','1','2');
//这里数字0-9数字任意添加，当然了最多10个数字
要求写一个函数比如：getCombination($data，2)，其结果为唯一性排序，每个组合数字不同，比如：

01
02
12

像01和10算一种组合，因为组成的数字相同。

求getCombination($data，$n)这样的高效算法函数

php 算法

12 years, 8 months ago

jobgene

jobgene 12 years, 8 months ago

我也写了一个，完全实现了n个不同元素中取出m个元素的组合，而 @PanYue 写的对元素有限制（1、元素必须为等差数列；2、公差必须为 1）如 {2,5,4,3} ，{1,2,4,3} 这样的元素组合就有错误了。

我的实现方法如下：

举例从 5 个不同的元素中取 2 个元素组合，首先构造一个长度一样的数组，用 1 表示当前的组合：

  /*
  

  1 1 0 0 0  //默认组合，=> 12
  

  1 0 1 0 0  //将元素中最后一个 1 与 后边第一个 0 交互位置， => 13
  

  1 0 0 1 0  //同上 => 14
  

  1 0 0 0 1  //同上 => 15
  

  0 1 1 0 0  //当最后一个1后边没有出现0,则选取前一个出现的1(右->左)并且后边元素是0，以此类推，找到后，并将其后边出现过的的所有1移动到这个元素之后 => 23
  

  0 1 0 1 0  //同第2步 => 24
  

  0 1 0 0 1  //同上 => 25
  

  0 0 1 1 0  //同第5歩 => 35
  

  0 0 1 0 1  // => 35
  

  0 0 0 1 1  // => 45
  

  */

直到没有满足条件的数为止，所以以上组合有：12,13,14,15,24,25,35,45

实现代码：

  function combination($arr,$num) {
  

  

  $len = count($arr);
  

  $by = array_merge(array_pad(array(),$num,1),array_pad(array(),$len-$num,0));
  

  $ret = array();
  

  while(1) {
  

  $p = true;
  

  $tmp = '';
  

  for($i=0;$i<$len;$i++) {
  

  if($by[$i] == 1) {
  

  $tmp .= $arr[$i];
  

  if(isset($by[$i+1]) && $by[$i+1] == 0) $p = $i;
  

  }
  

  }
  

  $ret[] = $tmp;
  

  if($p === true) break;
  

  list($by[$p],$by[$p+1]) = array($by[$p+1],$by[$p]);
  

  $t = array_slice($by,$p+2);
  

  if(in_array(1,$t)) {
  

  rsort($t);
  

  array_splice($by,$p+2,$len,$t);
  

  }
  

  }
  

  return $ret;
  

  }
  

  

  //测试
  

  $arr = array(1,2,3,4); //元素可以是任意元素，{a,b,c,d},{1,5,6,7,2}
  

  echo "<pre>";
  

  print_r(combination($arr,3));

没有用递归，while循环的次数为：n!/((n-m)! m!)
对结果数可以通过组合数公式 c(n,m)=p(n,m)/m!=n!/((n-m)! m!) 验证

answered 12 years, 8 months ago

Yuukimi

Yuukimi answered 12 years, 8 months ago