首页 > 试题广场 >

下面程序的功能是输出数组的全排列。请填空。

[单选题]
下面程序的功能是输出数组的全排列。请填空。 
void perm(int list[], int k, int m)
{
    if (    )
    {
        copy(list,list+m,ostream_iterator<int>(cout," "));
        cout<<endl;
        return;
    }
    for (int i=k; i<m; i++)
    {
        swap(&list[k],&list[i]);
        (    );
        swap(&list[k],&list[i]);
    }
}


  • k!=m 和 perm（list，k+1，m）
  • k==m 和 perm（list，k+1，m）
  • k!=m 和 perm（list，k，m）
  • k==m 和 perm（list，k，m）
添加回答
推荐
sdlkfjjaqw头像 sdlkfjjaqw
B。k==m and perm(list,k+1,m);for循环的作用是为先把index值为k的元素后面的元素一次与index为k的元素交换,相当于得到index为k的元素可能的取值情况，然后使用递归得到index为k+1的元素位置可能的所有取值。然而对index为k的位置元素进行取值的时候，操作过后需要还原避免取下一个值的时候错误,因此就有了第二个swap操作。由上分析可知,第一个空格应该为k==m，当index值到了m的时候输出即可，因为index为m后面已经没有元素与其进行对调.
编辑于 2015-01-10 21:06:18 回复(0)
轩辕箭头像 轩辕箭
#include<iostream>
#include<iterator>
using namespace std;

//1、关键：先想函数作用：这个函数作用是输出从第k个位置到第m个数（第m-1个位置）的全排列 
void perm(int list[], int k, int m)
{
    if (k==m)
    {
        copy(list,list+m,ostream_iterator<int>(cout," ")); //拷贝迭代器，作用是将List中的元素逐个输出   
        cout<<endl;
        return;
    }
 
    for (int i=k; i<m; i++)  //初始状态 k=0,m=4; 
    {
        swap(list[k],list[i]); //i从第k个位置开始，一直到第m-1个位置，交换他们的值。假设函数已经执行完i=0了，此时k=0,i=1，交换后list成2134 
        perm(list,k+1,m); 
        //这时候执行函数（作用上面写了）：对于数组2134，输出第k+1个位置到第m-1个位置的全排列，即操作（list[1]到list[3]的全排列），也就是此时的list[0] = 2不变，后面三个数134的全排列 
        //而输出134的全排列依然是用到perm函数，再按函数作用来理解，1不变的时候输出34全排列，3不变的时候...4不变的时候...etc 
        //如果递归到k==m，此时第k个位置到第m-1个位置范围不存在，这时候函数就把刚才经过一系列交换操作得到的数组输出
        swap(list[k],list[i]); //经过一系列操作之后得到了以list[1]=2开头的全排列，这个时候交换回来，list还得是原来的list1234，此时i++，再进行list[2]=3作为开头的一系列操作。 
    }
}

int main(){
    
    int list[4] = {1,2,3,4};
    perm(list,0,4);    
    
    cout<<"---------"<<endl;
    perm(list,2,4); //为了便于理解函数作用，加一个这个，则输出 1234与1243 
    
}

编辑于 2017-10-10 17:01:07 回复(3)
kuring头像 kuring
题目中存在某些问题，正确的函数写法应该这样。 
void perm(int list[], int k, int m)
{
    if (k==m)
    {
        copy(list,list+m,ostream_iterator<int>(cout," "));
        cout<<endl;
        return;
    }

    for (int i=k; i<m; i++)
    {
        swap(list[k],list[i]);
        perm(list,k+1,m);
        swap(list[k],list[i]);
    }
}

发表于 2015-01-23 10:42:15 回复(6)
努力去BAT的女子头像 努力去BAT的女子
依次将每一个元素放在最前面（本来就在最前面），对后面的子串进行全排列，当子串大小为1的时候可以直接打印数组，然后将数组回溯回原来的状态。
发表于 2015-07-17 10:10:25 回复(1)
JeonBoRam头像 JeonBoRam
想想嘛。。假如是。。k!=m，那岂不是一开始进入函数就输出一次然后返回了，不再有后面的循环递归。假如是perm（list，k，m），岂不是死循环？所以选B
发表于 2016-08-29 22:21:24 回复(0)
ClusterSocketListenThread头像 ClusterSocketListenThread 
#include <stdio.h>
#include <iterator>
#include <iostream>

using namespace std;
void swap( int *p, int *q)
{
	int temp;
	temp = *p;
	*p = *q;
	*q = temp;
}
void perm(int list[], int k, int m)
{
    if (  k==m  )
    {
        copy(list,list+m+1,ostream_iterator<int>(cout," "));
        cout<<endl;
        return;
    }
    for (int i=k; i<=m; i++)
    {
        swap(&list[k],&list[i]);
        (  perm(list,k+1,m)  );
        swap(&list[k],&list[i]);
    }
}

int main(void)
{
	int A[3] = {1,2,3};
	perm(A, 0, 2);
}

发表于 2016-08-28 16:53:05 回复(1)
努力工作lnm头像 努力工作lnm

/*--------------------------------------------------------------------------------------
输出数组的全排列。
void perm(int list[], int k, int m);

k: 你要选择全排元素的开始元素下标
如k =0：只全排列从0开始的元素
如k =1：只全排列从1开始的元素，0号位置不参与排列

m: 数组元素结束的下标
如m =1：只全排列0~1  这俩个元素
如m =2：只全排列0 1 2这三个元素

int list[] = {5, 6, 7};

perm(list, 0, 1);
5 6
6 5

perm(list, 0, 2);
5 6 7
5 7 6
6 5 7
6 7 5
7 6 5
7 5 6

perm(list, 1, 2);
5 6 7
5 7 6
--------------------------------------------------------------------------------------*/
void perm(int list[], int k, int m) {
    if (k == m){//递归出口：考虑只重排一个元素[即k = m]
        copy(list, list + m + 1, ostream_iterator<int>(cout, " "));
        cout << endl;
        return;
    }
    for (int i = k; i <= m; i++) {//只考虑两个元素
        swap(list[k], list[i]);//递归前交换
        perm(list, k + 1, m);  //递归
        swap(list[k], list[i]);//交换后再换回来
    }
}







编辑于 2019-03-05 16:59:06 回复(0)
榴莲糯米冰淇淋头像 榴莲糯米冰淇淋
题目跟个鬼样的，随便看眼就能猜出选项，但敲题目的时候就不能认真校对一下吗？ 

void perm(int list[], int k, int m)
{
    if (k == m)
    {
        copy(list,list+m,ostream_iterator<int>(cout," "));
        cout<<endl;
        return;
    }
    for (int i=k; i<m; i++)
    {
        swap(list[k],list[i]);
        perm(list, k+1, m);
        swap(list[k],list[i]);
    }
}

int main( void )
{
    int list[] = { 1, 2, 3 };
    perm(list, 0, 3);
} 







发表于 2021-09-02 19:36:50 回复(0)
DBest头像 DBest
全排列的实现
1）递归的思想
void permutation(char* a,int k,int m) 
{ 
    int i,j;
    if(k==m)
    {
        for(i=0;i<=m;i++)
            cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(j=k;j<=m;j++)
        {
            swap(a[j],a[k]);
            permutation(a,k+1,m);
            swap(a[j],a[k]);
        }
       
    }
} 
2)STL实现
void permutation(char* str,int length) 
{ 
    sort(str,str+length); 
    do 
    { 
        for(int i=0;i<length;i++) 
            cout<<str[i]; 
        cout<<endl; 
    }while(next_permutation(str,str+length)); 
} 
发表于 2017-09-08 11:00:30 回复(0)
元素周期表的十七君头像 元素周期表的十七君
参考：http://blog.csdn.net/morewindows/article/details/7370155/
为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。 首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。 然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道—— 全排列就是从第一个数字起每个数分别与它后面的数字交换。 找到这个规律后，递归的代码就很容易写出来了： 
//全排列的递归实现  
#include <stdio.h>  
#include <string.h>  
void Swap(char *a, char *b)  
{  
    char t = *a;  
    *a = *b;  
    *b = t;  
}  
//k表示当前选取到第几个数,m表示共有多少数.  
void AllRange(char *pszStr, int k, int m)  
{  
    if (k == m)  
    {  
        static int s_i = 1;  
        printf("  第%3d个排列\t%s\n", s_i++, pszStr);  
    }  
    else  
    {  
        for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列  
        {  
            Swap(pszStr + k, pszStr + i);  
            AllRange(pszStr, k + 1, m);  
            Swap(pszStr + k, pszStr + i);  
        }  
    }  
}  
void Foo(char *pszStr)  
{  
    AllRange(pszStr, 0, strlen(pszStr) - 1);  
}  
int main()  
{  
    printf("         全排列的递归实现\n");  
    printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");  
    char szTextStr[] = "123";  
    printf("%s的全排列如下:\n", szTextStr);  
    Foo(szTextStr);  
    return 0;  
}

编辑于 2017-05-02 19:31:22 回复(0)
Z--Z头像 Z--Z
void perm(int list[], int k, int m)
{
    if(k == m){
        copy(list, list+m+1, ostream_iterator<int>(cout, ""));//复制list从0->m 到 标准输出
        cout<<endl;
        return ;
    }
    for (int i=k; i<=m; i++)
    {
        swap(list[k],list[i]);
        perm(list,k+1,m);
        swap(list[k],list[i]);
    }
}
发表于 2017-01-07 10:10:37 回复(0)
牛客481035号头像 牛客481035号
递归，选b
发表于 2015-09-04 21:28:17 回复(1)
never&doubt头像 never&doubt
 说一些我对递归思想的理解：递归的思想类似归纳思想，首先考虑递归一定要学会简化思维，不能想的太深，而是只考虑一个层次的变化；否则就会陷入思维的误区；
以这道题为例，假设是一个长度为4的数组，a、b、c、d
首先应该先明白什么是一个长度为n的数组的全排列：第一个位置有n种可能，第二个位置有n-1中可能.....所以总共有n！个全排列；
递归思想：首先一个循环让a、b、c、d分别作数组首字母，也就是第一个位置的n种可能；然后不要再考虑第二个位置、第三个位置....这样就相当于把递归展开考虑，不可能想完；而是默认我们的算法可以得到剩下n-1个位置的全排列，进行递归[perm（list，k+1，m）]；
接下来再考虑出口就行了，也就是当最后只剩下一个位置没有确定时，k==m时，把数组打印出来即可；
总的来说，考虑递归就要先默认函数正确，然后在函数的基础上设计这个函数；
发表于 2017-03-04 14:14:23 回复(10)
牛客440592066号头像 牛客440592066号
假设数组123，k＝0，m＝3，递归就是一环扣一环，直到最底层循环k＝3的时候，结果输出123，然后退出最底层循环，再倒退回k＝2的状态，此时k＝2是最底层循环，结果输出132，（但是也是在1开头的循环里，要递归回去才能到2开头的循环里，2开头的循环里也有k＝3时的最底层循环）以此类推？我认为输出全队列的方式，时间复杂度很高，很浪费资源
发表于 2021-07-18 14:03:15 回复(0)
牛客563154472号头像 牛客563154472号
 for(inti=k; i<=m; i++)
    {
        swap(&list[k],&list[i]);
        (    );
        swap(&list[k],&list[i]);
    }
题目有点小问题，应该是i<m，不然下标越界了，编译运行出来是乱的
发表于 2020-11-28 10:05:46 回复(0)
Being-toward-death头像 Being-toward-death
这个代码的递归结束条件写的很糟糕！
perm(list, k+1, m); 很容易理解，交换确定区间[k, m]的第一个元素，然后将区间确定问题缩小到区间[k+1, m]；
但是直觉上每一个调用 perm，list 有序状态就是一个排列，而不是刻意体现出没有元素需要交换k == m才递归终结；
这种写法正确的原因在于循环中，第一次交换的是一个dummy op! 即 swap(list[k], list[k]);
比较有表现力的代码：
void perm(list& lst, int s, int e) 
{
    print(list);
    for (int i = s + 1; i <= e; i++) {
         swap(lst[s], lst[i]);
        perm(lst, s+1, e);
        swap(lst[s], lst[i]);
    }
}
发表于 2020-04-30 14:22:45 回复(0)
HUST_zxs头像 HUST_zxs
题目又没交代清楚，应该说是某个数组的从数组下标k到数组下标m的元素的全排列。递归思想仅从宏观上的单层递归思考，好理解，细推逐层调用，好难，容易想懵。
发表于 2018-10-04 18:24:56 回复(0)
Hairui201809121128157头像 Hairui201809121128157
根据递归结束条件可知k和m的值是变化的
发表于 2018-09-18 01:04:48 回复(0)
流风逐云头像 流风逐云

1 - n-1的全排列为（n-1）!

1 - n的全排列为（n）! = n * （n-1）!

高中时候理解这个递推公式；全排列n是在n-1个数的全排列基础上插入第n个数，共有n种插入方法

现在看了这个题也可以这样理解，在n-1个数的全排列基础上，将n插到第0个位置，然后从0个位置开始，第0号位置与其他1 - n-1号位置元素交换，交换得到1 + n-1种序列（插入0位置也算一种）。上面这个算法就是按照这个思路递归的。

void perm(int list[], int k, int m)
{
    if (k == m)
    {
        copy(list, list + m+1, ostream_iterator<int>(cout, " "));
        cout << endl;
        return;
    }
    for (int i = k; i <= m; i++)
    {
        if (i == k) {
            perm(list, k + 1, m);
        }
        else {
            swap(list[k], list[i]);;
            perm(list, k + 1, m);
            swap(list[k], list[i]);
        }
    }
}

加个if判断可以较少和自身位置元素交换，可以减少交换次数。性能来说，对于int数组，数组元素和自身交换需要时间和if判断所消耗时间差不多。但对于交换需要较长时间的类型，就会有比较好的效率
对与int[8]{ 1,2,3,4,5,6,7,8};源代码需要交换13856次，改进后代码需要交换80638次

编辑于 2018-06-05 12:00:28 回复(0)
obviouskkk头像 obviouskkk

题目代码有误，正确的完整可运行代码如下：

 #include <iostream>
 #include <algorithm>
 #include <iterator>

 void perm(int list[], int k, int m)
 {
     if (k == m)
     {
         copy(list, list + m + 1, std::ostream_iterator<int>(std::cout," "));
         std::cout << std::endl;
         return;
     }
     for (int i = k; i <= m; i++)
     {
         std::swap(list[k], list[i]);
         (perm(list, k + 1, m));
         std::swap(list[k],list[i]);
     }
 }


 int main(int argc, const char* argv[])
 {
     int list[] = {1, 2, 3, 4 ,5};
     perm(list, 0, 4);
     return 0;                                                                
 }
发表于 2018-02-04 22:10:21 回复(0)
视觉算法工程师头像 视觉算法工程师

直观点，不用思考就选B

发表于 2017-08-30 14:24:41 回复(0)
提交观点

问题信息

C++ 迅雷
来自：C/C++工程师能力评估
上传者：小海豹
难度：
25条回答 21006浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号