Generating Permutations Generating all permutations of the numbers 1, 2,…,n. Based on the assumption that if we can generate all the permutations of n-1 numbers,then we can get algorithms for generating all the permutations of n numbers
Generating Permutations ◼ Generating all permutations of the numbers 1, 2, …, n. ◼ Based on the assumption that if we can generate all the permutations of n-1 numbers, then we can get algorithms for generating all the permutations of n numbers
Generating Permutations Generate all the permutations of the numbers 2, 3,...,n and add the number 1 to the beginning of each permutation. Generate all permutations of the numbers 1,3, 4,...,n and add the number 2 to the beginning of each permutation. Repeat this procedure until finally the permutations of 1,2,...n1 are generated and the number n is added at the beginning of each permutation
Generating Permutations ◼ Generate all the permutations of the numbers 2, 3, …, n and add the number 1 to the beginning of each permutation. ◼ Generate all permutations of the numbers 1, 3, 4, …, n and add the number 2 to the beginning of each permutation. ◼ Repeat this procedure until finally the permutations of 1, 2, …, n-1 are generated and the number n is added at the beginning of each permutation
Input:A positive integer n; Output:All permutations of the numbers 1,2,...,n; 1.for 1to n ■ 2. L永←- 3.end for; 4.perm(1); perm(m) 1.if m=nthen output A1... 2.else ■ 3. for imto n 4. interchange Ai]and Am]; //Add one number at the beginning of the permutation 5. perm(m+1); //Generate permutations for the left numbers 6. interchange A]and Am]; 7. end for; 8.end if;
◼ Input: A positive integer n; ◼ Output: All permutations of the numbers 1, 2, …, n; ◼ 1. for j1 to n ◼ 2. P[j]j; ◼ 3. end for; ◼ 4. perm(1); ◼ perm(m) ◼ 1. if m=n then output P[1…n] ◼ 2. else ◼ 3. for jm to n ◼ 4. interchange P[j] and P[m]; ◼ //Add one number at the beginning of the permutation ◼ 5. perm(m+1); ◼ //Generate permutations for the left numbers ◼ 6. interchange P[j] and P[m]; ◼ 7. end for; ◼ 8. end if;
Generating Permutations a What is the recursion process? Write codes to implement the algorithms
Generating Permutations ◼ What is the recursion process? ◼ Write codes to implement the algorithms
Generating Permutations What's the performance of the algorithm Generating Permutations? √Time Complexity? √Space Complexity?
Generating Permutations ◼ What’s the performance of the algorithm Generating Permutations? ✓ Time Complexity? ✓ Space Complexity?