Description

Given a set of n≧1 elements, the problem is to print all possible permutations of this set. For example, if the set is (1,2,3), then the set of permutations is {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1), (3,1,2)}.

 

<Hint1>

Looking at the case of four elements (1,2,3,4). The answer can be constructed by writing

1. ‘1’ followed by all the permutations of (2,3,4)
2. ‘2’ followed by all the permutations of (1,3,4)
3. ‘3’ followed by all the permutations of (1,2,4)
4. ‘4’ followed by all the permutations of (1,2,3)

 

<Hint2>

A recursive method to implement the above idea is as follows:

Consider the case of (1,2,3,4), that is, n=4.

1. Place the set elements in a global array, and set the position index “k” as 0.
2. Use a for-loop to “swap” (or exchange) the 1^st element with the 1^st element, the 2^nd element, the 3^rd element, and the 4^th element, respectively.
   • In each loop-iteration:
     1. increment the position index “k” by 1 (for considering only the remaining elements in the following recursive call);
     2. use the updated k to recursively call your permutation function;
     3. note that because you use a global array, remember to swap back the two elements after the iteration.
3. In a recursive-call path, when k reaches n, it means that you get a possible permutation.

 

Note that

1.      This problem involves three files.

• function.h: Function definition of show, Swap and Perm.
• function.c: Function describe of show, Swap and Perm.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

#ifndef FUNCTION_H #define FUNCTION_H void show(int n); void Swap(int k, int i); void Perm(int k, int n); char list[10]; #endif

main.c

#include <stdio.h> #include "function.h" int main(void) { int num, i; scanf("%d",&num); for(i=0; i<num; i++) list[i]='1'+i; Perm(0,num); return 0; }

function.c

#include <stdio.h> ​#include "function.h" void show(int n) { int i; printf("(%c", list[0]); for (i=1; i<n; i++) { printf(",%c", list[i]); } printf(")\n"); } void Swap(int k, int i) { /*your code*/ } void Perm(int k, int n) { /*your code*/ }

Input

The decimal number n that represents the number of elements in the set.

(1≦n≦5)

Output

In the output you should print all the permutations.

Be sure to add a newline character '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10833.c

Partial Judge Header

10833.h

Tags

Discuss

Description

Given a link list structure named Node.

 

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Use this structure to implement a increasing integer link list.

 

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head); void freeList(Node*); int main() { Node *head = NULL; Node *temp; int data; while(1){ scanf("%d", &data); if (data >= 0) { insert_increase_list(&head, data); } else break; } printList(head); freeList(head); return 0; } void freeList(Node *head) { Node *temp; for(temp=head; temp!=NULL; temp=head) { head = head->next; free(temp); } } void printList(Node *head) { Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } printf("\n"); }

function.h

#include <stdio.h> #include <stdlib.h> typedef struct _Node { int data; struct _Node *next; } Node; void insert_increase_list(Node**, int);

Input

A non negative integer data per rows, if input is smaller then 0 then exit the while loop and exit the program.

Output

Please follow the output of program

Sample Input  Download

Sample Output  Download

Partial Judge Code

10945.c

Partial Judge Header

10945.h

Tags

Discuss

Description

版本：

20180311

 

使用說明：

請下載code或header（兩個是同個檔案）

把附檔名從.cpp改成.zip

解壓縮後

reference>en>cpp.html

即可看到官方文件

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

11462.cpp

Partial Judge Header

11462.h

Tags

Discuss

Description

Please implement insertion sort algorithm to sort a sequence of number in ascending order, and show the sequence of number after each iteration.

The insertion sort algorithm is shown in following:

The array is composed of two regions, sorted region and input region. At the beginning, the first element is considered sorted.

 

Array: 7 5 6 8 4 3 2 1

Sorted:(7)

Input:(5, 6, 8, 4, 3, 2, 1)

 

At each iteration, the first element in the input region is fetched, and will be inserted into the sorted region. To find the corrected location, the fetched element is compared with each element from the end of sorted region iteratively; if the fetched element is larger than the compared one, just swap them.

 

For example, in the first iteration, 7 is fetched from the input region.

Array: 7 5 6 8 4 3 2 1

Sorted:(7)

Fetch: 5

Input:(6, 8, 4, 3, 2, 1)

 

After the first iteration, the array becomes:

Array: 5 7 6 8 4 3 2 1

Sorted:(5, 7)

Input:(6, 8, 4, 3, 2, 1)

 

In the second iteration, 6 is fetched:

Array: 5 7 6 8 4 3 2 1

Sorted:(5, 7)

Fetch: 6

Input:(8, 4, 3, 2, 1)

 

After the second iteration, the array becomes:

Array: 5 6 7 8 4 3 2 1

Sorted:(5, 6, 7)

Input:(8, 4, 3, 2, 1)

 

If there are N elements, N-1 iterations is needed. The Sample Output shows the full results of the example.

Input

There are 2 lines input.

The first line contains a integer n, indicating the total number of integers would be sorted. (n <= 100000)

The second line consists of the integers being sorted.

Output

Show the sequence of number after each iteration.

If the input has n numbers, the output would have n-1 lines.

note: print a space before each number, and print '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss