V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
itfanr
V2EX  ›  程序员

如何输出一个数组的全排列?

  •  
  •   itfanr ·
    itfanr · 2013-09-18 16:37:09 +08:00 · 7441 次点击
    这是一个创建于 4085 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数组为:1 2 3 4 5 6

    语言不限

    感觉好难啊!
    27 条回复    1970-01-01 08:00:00 +08:00
    xoyo
        1
    xoyo  
       2013-09-18 16:52:36 +08:00
    用DFS就可以了~
    itfanr
        3
    itfanr  
    OP
       2013-09-18 17:29:44 +08:00
    @llbgurs 果然厉害
    itfanr
        4
    itfanr  
    OP
       2013-09-18 17:31:40 +08:00
    @xoyo ?啥东东
    skyahead
        5
    skyahead  
       2013-09-18 17:38:19 +08:00
    昨天刚好写了一个python,不过输入是字符串!

    def get_permutations(s):
    result = []

    assert len(s) is not 0 # sanity check

    if len(s) == 1:
    result.append(s)
    else: # len >= 2
    for i in range(len(s)):
    curr = s[i]

    # rest of the string
    if i == 0: # first in the string
    rest = s[1 : ]
    elif i == len(s) - 1: # last in the string
    rest = s[ : i ]
    else: # those in the middle
    rest = s[0 : i] + s[i + 1 : ]

    for a in get_permutations(rest): # get all the premutations of [s - curr]
    result.append(curr + a)

    return result

    if __name__ == "__main__":
    s = '1234'
    print get_permutations(s)
    txx
        6
    txx  
       2013-09-18 17:41:54 +08:00
    https://gist.github.com/rpplusplus/6606861

    随手写了个 c 的 居然没debug 就过了.....
    momou
        7
    momou  
       2013-09-18 17:55:48 +08:00
    前天刚学习过的JS:
    /*
    全排列(递归交换)算法
    1、将第一个位置分别放置各个不同的元素;
    2、对剩余的位置进行全排列(递归);
    3、递归出口为只对一个元素进行全排列。
    */
    function swap(arr,i,j) {
    if(i!=j) {
    var temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    }
    }
    var count=0;
    function show(arr) {
    document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
    }
    function perm(arr) {
    (function fn(n) { //为第n个位置选择元素
    for(var i=n;i<arr.length;i++) {
    swap(arr,i,n);
    if(n+1<arr.length-1) //判断数组中剩余的待全排列的元素是否大于1个
    fn(n+1); //从第n+1个下标进行全排列
    else
    show(arr); //显示一组结果
    swap(arr,i,n);
    }
    })(0);
    }
    permutations([1,2,3,4,5,6]);
    kid177
        8
    kid177  
       2013-09-18 18:46:48 +08:00
    #include <algorithm>

    next_permutation
    xoyo
        9
    xoyo  
       2013-09-18 19:29:28 +08:00
    @itfanr Depth first search 深度优先搜索。比如@txx的代码就是。
    leunggamciu
        10
    leunggamciu  
       2013-09-18 20:52:37 +08:00
    刚学C的时候写的,用递归比较好理解,可以[先固定第一个字符,对余下的字符作全排列],因为一个字符的全排列就是它本身,所以这里就构成了一个递归

    void prem(char *list,int i,int n)
    {
    int j;
    if(i==n)
    {
    for(j=0;j<=n;j++)
    printf("%c",list[j]);
    printf(" ");
    }
    else
    {
    for(j=i;j<=n;j++)
    {
    SWAP(&list[i],&list[j]);
    prem(list,i+1,n);//处理子序列
    SWAP(&list[i],&list[j]);
    }
    }
    return;
    }

    char list[] = "1234";
    prem(list,0,3);
    leunggamciu
        11
    leunggamciu  
       2013-09-18 20:54:08 +08:00
    @leunggamciu 请原谅我单词拼错了!
    amyangfei
        12
    amyangfei  
       2013-09-18 21:28:01 +08:00
    for i in itertools.permutations('123456', len('123456')):
    print ''.join(i)
    ctrlaltdeletel
        13
    ctrlaltdeletel  
       2013-09-18 22:15:28 +08:00
    dreamersdw
        14
    dreamersdw  
       2013-09-18 22:28:04 +08:00   ❤️ 1
    Karsa
        15
    Karsa  
       2013-09-18 23:13:34 +08:00
    <code>
    def pickOne (array1, array2) :
    length = len (array2)
    if length == 0 :
    return
    for i in range (0, length) :
    tempArray1 = array1[:]
    tempArray2 = array2[:]
    moveArrayItem (tempArray1, tempArray2, i)
    print (tempArray1)
    pickOne (tempArray1, tempArray2)

    def moveArrayItem (array1, array2, index) :
    if index < len(array2) :
    array1.append (array2.pop(index))

    array = [1,2,3,4,5,6]
    tempArray = []
    pickOne (tempArray, array)

    </code>
    laskuma
        16
    laskuma  
       2013-09-18 23:16:54 +08:00
    @xoyo 略想吐槽。。
    wang2191195
        18
    wang2191195  
       2013-09-19 00:36:17 +08:00
    @fantasticfears 高端洋气c++11
    其实现在非常喜欢来数组了。。。int a[] = {1,2,3,4,5,6};
    kotokz
        19
    kotokz  
       2013-09-20 00:52:53 +08:00
    echo "123456" | ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join “ ”}'
    xlhuang
        20
    xlhuang  
       2013-09-20 02:17:51 +08:00
    <code>
    <pre>
    var result = [];
    function permutation1(arr) {
    perm1(arr, 0);
    }
    function perm1(arr, index) {
    var n = arr.length;
    if (index === n - 1) {
    result.push(arr.slice());
    return false;
    } else {
    for (j = index; j < n; ++j) {
    swap(arr, j, index);
    arguments.callee(arr, j + 1);
    swap(arr, j, index);
    }
    }
    }
    function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
    }
    </pre>
    </code>
    xlhuang
        21
    xlhuang  
       2013-09-20 02:56:28 +08:00
    tioover
        22
    tioover  
       2013-09-20 22:30:42 +08:00
    http://gist.github.com/tioover/6638449

    其实应该用Scheme 来写。
    yukirock
        23
    yukirock  
       2013-09-21 02:16:36 +08:00
    《组合数学》中提到过一种全排列升成算法。

    给定一个整数 k,在其上方标记一个左箭头或右箭头以示方向,如:

    < >
    k 或 k

    对于 {1..k} 的一个排列,对于其中每一个数都给定一个方向。如果一个整数 k 的箭头指向一个与其相邻但是比它小的整数,那么 k 即为「活动的」。例如对于

    >>><>>
    263154

    356 是活动的。

    可以得出如下结论:

    * 1 一定不是活动的,因为 1 是最小的整数。
    * 除了以下两种情况,{1..n} 中最大的整数 n 总是活动的:n 在最左边且它的箭头朝左,或 n 在最右边且它的箭头朝右。

    算法如下。



    <<..<
    12..n

    开始。

    当存在一个活动的整数时,执行:

    1. 求出最大的活动整数 m
    2. 交换 m 及其箭头所指的与其相邻的整数
    3. 交换所有满足 p>m 的整数 p 的方向。

    以 n=4 为例:

    <<<<
    1234

    <<<<
    1243

    <<<<
    1423

    <<<<
    4123

    ><<<
    4132

    <><<
    1432

    <<><
    1342

    <<<>
    1324

    <<<<
    3124

    <<<<
    3142

    (略)

    <<>>
    2134

    到 2134 中没有活动整数,算法终止。此时已经打出 {1234} 的全排列。
    tioover
        24
    tioover  
       2013-09-21 02:23:05 +08:00
    我之前发的怎么没有了?

    http://gist.github.com/tioover/6638449
    coldear
        25
    coldear  
       2013-09-21 06:03:31 +08:00
    kedebug
        26
    kedebug  
       2013-09-21 11:47:10 +08:00
    建议楼主平时多积累些基础的算法知识,像全排列这样经典的递归算法应该信手拈来才是。
    itfanr
        27
    itfanr  
    OP
       2013-09-21 12:39:46 +08:00
    @kedebug 笔试考了 拈不来
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3605 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 04:48 · PVG 12:48 · LAX 20:48 · JFK 23:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.