在dev c++中用c语言写一个全排列（不能用递归）,该怎么处理

在dev c++中用c语言写一个全排列（不能用递归）
在dev c++中用c语言写一个全排列（不能用递归）指针尽量避免使用给出代码同时有注释另外算法也写上（设计思路）

------解决方案--------------------
基本思想是:
1.找到所有排列中最小的一个排列P.
2.找到刚刚好比P大比其它都小的排列Q,
3.循环执行第二步,直到找到一个最大的排列,算法结束.
下面用数学的方法描述:
给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )
找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)
从Pmin开始,总是目前得到的最大的排列为输入,得到下一个排列.
方法为:
1.从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个Pi，使Pi < P(i+1)。
若找不到这样的pi，说明我们已经找到最后一个全排列，可以返回了。
2.在 P(i+1)P(i+2)Pn 中,找到一个Pj,便得 Pj"刚刚好大于"Pi.
("刚刚好大于"的意思是:在 P(i+1)P(i+2)Pn 中所有大于Pi的元素构成的集合中最小的元素.)
3.交换 Pi , Pj 的位置.注意:此处不改变i和j的值,改变的是Pi和Pj.
4.交换后， P1P2P3Pn 并不是准确的后一个排列。因为根据第1步的查找，我们有P(i+1) > P(i+2) > . > Pn
即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.

C/C++ code


//交换数组a中下标为i和j的两个元素的值
void swap(int* a,int i,int j)
{
    a[i]^=a[j];
    a[j]^=a[i];
    a[i]^=a[j];
}
 
//将数组a中的下标i到下标j之间的所有元素逆序倒置
void reverse(int a[],int i,int j)
{
    for(;i<j;++i,--j)
    {
         swap(a,i,j);
    }
}
 
void print(int a[],int length)
{
    for(int i=0;i<length;++i)
         cout<<a[i]<<" ";
    cout<<endl;
}
 
//求取全排列，打印结果
void combination(int a[],int length)
{
    if(length<2) return;
 
    bool end=false;
    while(true)
    {
         print(a,length);
        
         int i,j;
         //找到不符合趋势的元素的下标i
         for(i=length-2;i>=0;--i)
         {
             if(a[i]<a[i+1]) break;
             else if(i==0) return;
         }
 
         for(j=length-1;j>i;--j)
         {
             if(a[j]>a[i]) break;
         }
        
         swap(a,i,j);
         reverse(a,i+1,length-1);
    }
}

------解决方案--------------------

C/C++ code


#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

int func(const int *array, int size)
{
    int *tab;
    int cnt, cur;
    int i;
    
    if (NULL == array || size <= 0)
    {
        return 0;
    }

    cnt = 0;
    cur = 0;
    if (NULL == (tab = (int *)malloc(size * sizeof(int))))
    {
        return 0;
    }
    tab[0] = -1;
    while (cur >= 0)
    {
        do
        {
            tab[cur] += 1;
            for (i = 0; i < cur; ++i)
            {
                if (tab[cur] == tab[i])
                {
                    break;
                }
            }
        }while (tab[cur] < size && i != cur);
        
        if (tab[cur] < size)
        {
            if (size - 1 == cur)
            {
                for (i = 0; i < size; ++i)
                {
                    printf("%d ", array[tab[i]]);
                }
                printf("\n");
                
                ++cnt;
            }
            else
            {
                cur += 1;
                tab[cur] = -1;
            }
        }
        else
        {
            cur -= 1;
        }
    }
    
    free(tab);
    
    return cnt;
}

int main()
{
    int a[] = {1, 2, 3, 4, 5};
    printf("共有%d中全排列情况\n", func(a, sizeof(a) / sizeof(a[0])));
    
    system("pause");
    return 0;
}

在dev c++中 用c语言写一个全排列（不能用递归）,该怎么处理

相关推荐

在dev c++中用c语言写一个全排列（不能用递归）,该怎么处理