As you know from Discrete Math, a permutation is any possible ordering of the di

Question

As you know from Discrete Math, a permutation is any possible ordering of the distinct items of a set S. If |S| = n, there are n! permutations. This means that for large sets, it is computationally infeasible to generate all possible permutations. One well-known algorithm for generating set permutations (at least for small sets) is presented below:

ALGORITHM Johnson-Trotter(n)

// Input: a positive integer n

// Output: A list of all permutations of {1, 2, %u2026, n}

initialize the first permutation as 1 2 %u2026 n with directions pointing left

while the last permutation has a mobile element

find its largest mobile element k

swap k and the element to which k is directed

reverse the direction of all elements that are larger than k

add the new permutation to the list

Note: an element is mobile if its direction points to a smaller adjacent element.

Example:

%uF0AC%uF0AC%uF0AC %uF0AC%uF0AC%uF0AC %uF0AC%uF0AC%uF0AC %uF0AE%uF0AC%uF0AC %uF0AC%uF0AE%uF0AC %uF0AC%uF0AC%uF0AE

1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3

REQUIREMENTS:

Design and implement a program to generate all permutations of the set of least n positive integers.

INPUT:

an integer n with 1 %uF0A3 n %uF0A3 25.

OUTPUT:

The tag %u201CThere are x permutations of the set {1, 2, %u2026, n}:%u201D, where x = n!

a list of all permutations of the set {1, 2, %u2026, n}, one per line.

Explanation / Answer

#include<stdio>

using namespace std;

int main()

{int N;

cout<<"Enter the value of n:"<<endl;

cin>>N

perm(N);

system("pause");

return 0;

}

void perm(int N) {

int[] p = new int[N];   

int[] pi = new int[N];

int[] dir = new int[N];   

for (int i = 0; i < N; i++) {

dir[i] = -1;

p[i] = i;

pi[i] = i;

}

perm(0, p, pi, dir);

}

void perm(int n, int[] p, int[] pi, int[] dir) {

if (n >= p.length) {

for (int i = 0; i < p.length; i++)

cout<<p[i]+1;

cout<<endl;

return;

}

perm(n+1, p, pi, dir);

for (int i = 0; i <= n-1; i++) {

int z = p[pi[n] + dir[n]];

p[pi[n]] = z;

p[pi[n] + dir[n]] = n;

pi[z] = pi[n];

pi[n] = pi[n] + dir[n];

perm(n+1, p, pi, dir);

}

dir[n] = -dir[n];

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.