使用ruby实现的全排列算法

numAry = [1,2,3]

def swap(ary,p,n)
  temp = ary[p]
  ary[p] = ary[n]
  ary[n] = temp
end

def perm(ary,k)
  if k == 1 #注意这里的判断条件和方法perm2中比较一下
    puts ary.join(' ')
  else
    ((ary.size-k)...ary.size).each do |i| #循环的条件，注意与perm2比较
      swap(ary,i,ary.size - k)
      perm(ary,k-1)#这里是减一
      swap(ary,i,ary.size-k)
    end
  end
end

#另外一种算法
def perm2(ary,k)
  if k == ary.size - 1 #注意比较
    puts ary.join(' ')
  else
    (k...ary.size).each do |i| #注意比较
      swap(ary,k,i)
      perm2(ary,k+1)#这里是加一
      swap(ary,k,i)
    end
  end
end

puts "使用perm运行结果"
perm(numAry,numAry.size)
puts "现在的numAry"
puts numAry.join(' ')
puts "使用perm2运行结果"
perm2(numAry,0)！

用这个算法的实现相当于一直在操作一个数组，一直往符合条件的地方发展，符合条件输出之后又变回原来的样子（通过swap方法），也就是说，整个算法运行结束，原来的数组又变回原来的样子。我中间一度没有真正理解第二个swap存在的意义，如果不交换回来，那相当于没有原来的样子做参考，那也就是将不知道自己的进度，那必将走向分叉路

书中的算法代码：

void perm(int A[],int k,int n){//参数k是当前递归层需完成排列的元素个数
    int i;
    if(k == 1)//已构成一个排列，将其输出
        for(i = 0;i < n;i++)
            cout << A[i];
    else
        for(i = n - k;i < n;i++){
            swap(A[i],A[n-k]);//swap为完成元素互换的函数
            perm(A,k-1,n);
            swap(A[i],A[n-k]);
        }
}

参考文章：
https://blog.csdn.net/z11176667078/article/details/77872063
http://www.cnblogs.com/zyoung/p/6764371.html

https://blog.csdn.net/wzy_1988/article/details/8939140