0

我对赋值有疑问，我们需要在 C++ 中为数字实现递归排列。这是部分有效但缺少一些数字的代码。我找不到问题出在哪里。

这段代码确实有效，但并不完全正确。

此代码采用具有该数组大小的数字数组。在这种情况下，我试图解决当我发送超过 3 个数字的数组时出现的问题。如果我发送 3 个数字，则输出为：

///
1 2 3 /
1 3 2 /
3 1 2 /
2 1 3 /
2 3 1 /
3 2 1 /

这种情况下的输出是正确的。但是当我将数组设置为 4 并发送它的大小 4 我得到：

///
1 2 3 4 /
1 2 4 3 /
1 4 2 3 /
4 1 2 3 / 
**2 1 3   /
2 3 1   /
3 2 1   /**
3 2 1 4 /
3 2 4 1 / 
3 4 2 1 /
4 3 2 1 /

输出部分正确，但缺少一些数字。

程序应该输出数组中所有可能的数字变化

#include <iostream>
using namespace std;

bool nextPermutation(int[],int);
void swap(int&, int&);
int Maxind(int[],int);
int Minind(int[],int);
void print (int[], int);
bool test (int[], int);
int fl=0;


int main() {
    int a[]={1,2,3,4};
    nextPermutation(a,4);
    return 0;
}


void print(int a[], int s) {
    for(int i=0; i<s; i++) 
    { 
        cout<<a[i]<<" "; 
    }
    cout<<endl;
}
bool nextPermutation(int a[], int s)
{
    int i=Maxind(a,s);
    if(fl==0)
        print(a,s);
    if(i!=0) {
        swap(a[i],a[i-1]);
        nextPermutation(a,s); 
    }

    else if(i==0 && test(a,s))
    {
        int p=a[0];
        for(int i=0; i<=s-2; i++)
            a[i]=a[i+1];
        fl=1;
        nextPermutation(a,s-1);
        a[s-1]=p;
        fl=0;
        nextPermutation(a,s);            
    }
    else 
        return false;
}

bool test (int a[], int s) {    
    if (Maxind(a,s)==0 && Minind(a,s)==s-1)
        return false;
    else
        return true;
}

void swap(int& a, int& b)
{
    int t=a; a=b; b=t;
}

int Maxind(int a[], int s)
{
    int m=a[0], ind=0;
    for(int i=0; i<s; i++) 
        if(m<a[i]) {
            m=a[i];
            ind=i;
        }
    return ind;
}

int Minind(int a[], int s)
{
    int m=a[0], ind=0;
    for(int i=0; i<s; i++) 
        if(m>a[i]) {
            m=a[i];
            ind=i;
        }
    return ind;
}
4

2 回答 2

1

您需要发送所有排列的可能性。

如果你改变你的main功能，你会得到解决方案。在主函数中添加一个loop并发送到nextPermutation(a, i)变量i 

int main() {
    for(int i = 1; i < 5; i++) {
        int a[]= {1,2,3,4};
        nextPermutation(a,i);
    }
    return 0;
}

你应该调试你的程序，而且我发现你的 s 值在这里下降：

else if(i==0 && test(a,s)) {
    int p=a[0];
    for(int i=0; i<=s-2; i++) {
        a[i]=a[i+1];
    }
    fl=1;
    nextPermutation(a,s-1);
    //*** careful you are decreasing s here and your output gives 3 numbers. !!***
    a[s]=p;
    fl=0;
    nextPermutation(a,s);
}
于 2013-09-04T06:47:41.687 回答
1

我刚刚修改了代码的 nextPermutation 方法，如下所示，它起作用了。

bool nextPermutation(int a[], int s)
{
    if(s == 0)
        return false;
    int i=Maxind(a,s);
    if(fl==0)
        print(a,s);
    if(i!=0) {
        swap(a[i],a[i-1]);
        if(fl == 0)
            nextPermutation(a,s); 
        else{    
            int temp = fl;
            fl = 0;
            nextPermutation(a,s+temp);
        }
    }
    else if(i==0){
        int p=a[0];
        for(int i=0; i<=s-2; i++)
            a[i]=a[i+1];
        a[s-1]=p;
        fl+=1;
        nextPermutation(a,s-1);
    }
    else 
        return false;
}

我还删除了 test 和 Minnd 方法，因为它们在我的代码中没有用。

于 2014-08-28T07:42:11.533 回答