Catalog

Preface

Topic introduction

sample input :

sample output :

introduce ：

The theory exists , Practice begins ！

Solution ：

Wrong scheme 1：

Wrong scheme 2：

Correct scheme 1：

summary ：

Love is worth years. Love is worth years .

Preface

QWQ Yesterday's PTA The experimental questions assigned by the teacher , It used to be a chapter a night , When I was thinking of finishing the small experimental questions assigned by the teacher in an instant today, and then writing a blog ,**（ Here is the word that will be harmonious ）, all night , The problem of full permutation is that the output cannot come out , I think how big a hole this small full arrangement problem can be ？？？ It has always been a partial mistake , I'll just knock , No look C standing , I think Lao Zi can learn recursion well , This little code is hard for me ？？？ therefore , The night went by , I wrote two full permutation algorithms , It's all partial mistakes , I just found out that , Things are not as simple as expected . The sorting of output results in the full permutation is required, rather than you output , Can ... So after asking the great God the correct answer , I suddenly realized ！！！

I'm a chicken dish ：[                                                         

Topic introduction

sample input :

3
1 2 3

sample output :

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Before starting, you can write it yourself to see if you can write it yourself ~ Pay attention to the output format ！

introduce ：

This problem , Needless to say, it is a recursive or recursive problem at first glance , I am not talented , Only recursion .. So how to recurse ？？

First of all, you have to look at this sort, you know ！ Look at that 3,1,2 and 3,2,1 First 1,2 after 2,1 such , I did it all night ,** Some test cases are wrong ！！！ Very annoying ！

This problem requires backtracking

The theory exists , Practice begins ！

Solution ：

Wrong scheme 1：

#include <stdio.h>
void swap(int *q,int *p)  
// Two number exchange functions , Note that the formal parameters of the function should use pointer variables , Only in this way can the data in the target array be changed ;
{
    int t;
    t = *q; // take q The data pointed to by the pointer is assigned to t;
    *q = *p;
    *p = t; // take t Assign the data in to p The position space pointed by the pointer ;
}
void f(int a[],int k,int m)
// Define a function for finding complete permutation , In the following recursion, this function is used as a known complete function ;
{
    int i;
    if(k==m)  // Flag for the end of recursion ;
    {
        for(i=0; i<=m; i++)
        {
            if(i==0)
                printf("%d",a[i]);
            else printf(",%d",a[i]);
        }
        printf("\n");
    }
    else
    {
        for(i=k; i<=m; i++)
        {
            swap(&a[k],&a[i]);
            f(a,k+1,m);
            swap(&a[k],&a[i]);
        }

    }
}
int main ()
{

    int array[11],i,t,n;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d",&n);
            for(i=0; i<n; i++)
            {
                scanf("%d",&array[i]);
            }
            f(array,0,n-1);
        }

    }
    return 0;

}

In this case, the latter two cases will be output first 3,2,1 Then the output 3,1,2 Not all right ！

Wrong scheme 2：

#include<stdio.h>
int a[10],c[10],n,d[10];//c Array marks the numbers that appear ,d The array is the array that records the answers 
void dfs(int i);
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		c[i]=0;// Initialize the count array 
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	dfs(0);
}
void dfs(int x)
{
	if(x==n)
	{
		for(int v=0;v<n;v++)
		{
			printf("%d ",d[v]);
		}
		printf("\n"); 
		return ;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(c[i]==0)
			{
				d[x]=a[i];
				//printf("%d ",a[i]);
				c[i]=1;
				dfs(x+1);
				c[i]=0;
			}
		}
	}
	
}

In this way, only one number can be entered , And not all cases are right （ Don't ask , I was going to steal the chicken ）

Correct scheme 1：

Recursive backtracking ：（ There are comments after the code ！！！）

#include<stdio.h>

void f(int *a, int p, int q)

{
    int j,i;// Loop variable 

    if(q == p)//  Recursive cut-off conditions ： Tail variable = Header variables , Output after cut-off .
    {
        
        for(i = 0 ; i <= q ; i++)
        {
            
            if(i == q)
            {
                printf("%d\n",a[i]);
            }//  Print the last 
            
            else printf("%d,",a[i]);//  Print the front 
       
        }
    }


    else// Recursion 
    {
        for(i = p ; i <= q ; i ++) // Traverse each of the arrays 
        {
            
            if(i == 0)
            {
                f(a, p + 1, q);// Arrange the second number and subsequent numbers 
            }// When p Is the first number of the array 
            
            else
            {
                
                int t = a[i];// Save it for a while 
                
                for(j = i - 1 ; j >= p ; j --)
                {
                    a[j + 1] = a[j];
                }
                
                a[p] = t ;// The first i Put the number first 

                f(a, p + 1 , q);// Use recursion to find the following Full Permutation 
                
                t = a[p];
                
                for(j = p + 1; j <= i ; j ++)
                {
                    
                    a[j - 1] = a[j];
                
                }
                
                a[i] = t;//  to flash back （ Put the first number at the end ）
            }

        }
    }
        
}


int main()
{
    int n ;
    scanf("%d",&n);
    int a[100] ;
    int i;
    for(i = 0 ; i < n ; i ++)
    {
        scanf("%d",&a[i]);
    }
    f(a, 0, n - 1);// Make a full arrangement 
}

summary ：

Let's talk about how this is recursive ！ Look at this ！ If input 123 Words , He will do this ！

  Green is the sequence of backtracking

The red ones are before and after printing data

Hey , Take a good look and you should be able to understand , A very simple recursive backtracking problem ！

That is to move every number to the first place and then move it back for backtracking ！ Moving each number to the first place can realize full arrangement ！

It's a little vague .. Should be able to understand , Wait until I finish the exam （ Painting the big cake ）

Love is worth years.
Love is worth years .