C\C++数字排列问题

Swarm

输入任意正整数n(n>=3)，要求输出由1,1,2,2,3,3,......,n,n等2n个数组成的数列，使得：
    两个“1”之间有1个数
    两个“2”之间有2个数
    两个“3”之间有3个数
    ......
    两个“n”之间有n个数
    如输入3，则输出231213或312132

可能没有或者有多种排列方式，要求全部输出。

我能想到的唯一思路是将这2n个数字全排列，然后把不符合要求的排序剔除掉。虽然空间复杂度只有O(n)，但这样的算法时间复杂度足足有O(n!)，这显然是不可接受的。希望有大家能帮萌新解决一下这个问题。谢谢大家！

千公子

我有一个思路，你可以参考下，比方说n=3,1[]1, 2()()2, 3{}{}{}3, 31[2](1)(3)2，成对出现去拼，n=4也同理41312432可以很快的拼出结果。

千公子

你可以弄一个字符串，然后写一个函数。

void func(int n, string s){
找到s第一个空位，
放下数字n，
然后隔n个位置把n放下。
如果该位置有数字，重新寻找第一位。
}

Swarm

千公子 发表于 2019-4-13 16:07
你可以弄一个字符串，然后写一个函数。

那这样的话是不是需要用到递归？先插入n，再插入n-1，一直到最后插入1？

千公子

Swarm 发表于 2019-4-14 10:19
那这样的话是不是需要用到递归？先插入n，再插入n-1，一直到最后插入1？

都可以吧，但是需要回溯，也就是全排列的思想，只不过是成对的排，用这个思路应该就排除112233这种情况，

Swarm

目前能够做到的就是这样……输入3和4都可以得到正确结果……
但当我输入5,的时候，本应该是没有结果，但是却告诉我程序运行出错……
应该有可能是内存溢出了？求大家帮忙看一下到底是怎么回事？

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

#define Max 100
int array[Max*2]={0};
int visit[Max][Max*2]={0};

typedef struct
{
        int no[Max];
        int posi[Max*2];
        int top;
}Stack;





void Inite(Stack *&s,int n)
{
        int i;
        s=(Stack *)malloc(sizeof(Stack));
        s->top=-1;
        for(i=n*2;i<Max*2;i++)
                array[i]=-1;
}





void Destroy(Stack *&s)
{
        free(s);
}





void Push(Stack *&s,int i,int p)                //入栈，填数字，将visit[p]记为1
{
        //入栈常规操作
        s->top++;
        s->no[s->top]=i;
        s->posi[s->top]=p;

        //将数字放进数组里
        array[p]=array[p+i+1]=i;

        //这个位置i试过了
        visit[i-1][p]=1;
}





void Pop(Stack *&s,int n)                                //出栈，数组恢复，重置visit
{
        int i,p;
        int j,k;

        //出栈常规操作
        i=s->no[s->top];
        p=s->posi[s->top];
        s->top--;

        //将数字从数组里取出
        array[p]=array[p+i+1]=0;

        //将出栈元素之前的所有元素的visit重置
        for(k=0;k<i-1;k++)
                for(j=0;j<n*2;j++)
                        visit[i-2][j]=0;
}





bool Empty(Stack *&s)
{
        return s->top==-1;
}





void PopAll(Stack *&s,int n)
{
        while(!Empty(s))
                Pop(s,n);
}





void Disp(int n)
{
        int i;
        int p,q;
        for(i=0;i<2*n;i++)
        {
                printf("%d ",array[i]);
        }
        printf("\n");
        for(p=0;p<n-1;p++)
                for(q=0;q<2*n;q++)
                        visit[p][q]=0;
        for(p=0;p<2*n;p++)
                array[p]=0;
}





void sort(Stack *&s,int n)
{
        int i=n,p,j;
        int count=0;
        while(1)
        {
                for(i;i>0;i--)                                //i用于计数
                {
                        for(p=0;p<2*n-i-1;p++)        //p用来定位
                        {
                                if(array[p]==0 && array[p+i+1]==0 && visit[i-1][p]==0)//这个位置和间隔i个位置都有空而且这个位置以前没放过
                                {
                                        Push(s,i,p);        //入栈，填数字，将visit[p]记为1
                                        break;
                                }
                        }
                        if(p==2*n-i-1)                                //所有位置都试过一遍了
                        {
                                Pop(s,n);                        //出栈，数组恢复，重置visit
                                i+=2;                                //重新排出栈的那个元素
                        }
                }


                //判断是否要打印
                for(j=0;j<n*2;j++)
                        if(array[j]==0)
                                goto next;
                Disp(n);
                i=n;
                PopAll(s,n);
                count++;


                //判断是否全都循环过一遍
next:        for(j=0;j<n-1;j++)
                        if(visit[n-1][j]==0)
                                goto end;
                break;
end:        ;
        }
        if(count==0)
                printf("无\n");
}





int main()
{
        int n;
        Stack *s;
        printf("Input a number:( must more than 0 and less than 101 )\n");
        scanf("%d",&n);
        Inite(s,n);
        sort(s,n);
        Destroy(s);
        return 0;
}

千公子

我今天做题做到了这个，就写了代码！你可以参考下！

标题：扑克序列

    A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。
    要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。

    请填写出所有符合要求的排列中，字典序最小的那个。

例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案

#include <iostream>

using namespace std;
struct num {
        int n;
        char c;
}A[4];

//结果
char arr[9];
// 使用过的字符标记上
bool used[4];
// 已经使用的字符数
int used_count = 0;
// 递归次数
int deep_num = 0;

void init() {
        for (int i = 0; i < 9; ++i) {
                arr[i] = '\0';
                if(i<4)
                        used[i] = false;
        }
}
void shift(int j) {
        ++deep_num;
        for (int i = j; i < 7; ++i) {

                for (int k = 0; k <= 3; ++k) {
                        if (used[k]) continue;
                        int nextidx = i + A[k].n;
                        if (nextidx > 7) continue;
                        // 找到合适位置
                        if (arr[i] == '\0' && arr[nextidx] == '\0') {
                                arr[i] = A[k].c;
                                arr[nextidx] = A[k].c;
                                used_count += 1;
                                used[k] = true;

                                shift(j + 1);

                                arr[i] = '\0';
                                arr[nextidx] = '\0';
                                used_count -= 1;
                                used[k] = false;
                        }
                }
        }
        
        if(used_count==4)
                cout << arr << endl;
}
int main() {
        
        A[0].n = 2;
        A[0].c = 'A';

        A[1].n = 3;
        A[1].c = '2';

        A[2].n = 4;
        A[2].c = '3';

        A[3].n = 5;
        A[3].c = '4';

        init();
        shift(0);
        cout << deep_num << endl;
        return 0;
}

思路还是上次和你说的思路！