Permutations by swapping: Difference between revisions
Content deleted Content added
→{{header|C++}}: Cut down the verbosity of unnecessary comments, and some overtly long variable names. |
|||
Line 87: | Line 87: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp> |
<lang cpp>/* |
||
/* |
|||
The following code generates the permutations of the first 4 natural numbers. |
The following code generates the permutations of the first 4 natural numbers. |
||
The permutations are displayed in lexical order, smallest to largest, with appropriate signs |
The permutations are displayed in lexical order, smallest to largest, with appropriate signs |
||
*/ |
*/ |
||
Line 97: | Line 96: | ||
//factorial function |
//factorial function |
||
long |
long |
||
fact(int size) |
|||
{ |
{ |
||
int i; |
int i; |
||
Line 112: | Line 112: | ||
//function to display the permutations. |
//function to display the permutations. |
||
void |
|||
Permutations(int N) |
|||
{ |
{ |
||
//indicates sign |
|||
short sign = 1; |
|||
⚫ | |||
unsigned short change_sign = 0; |
|||
⚫ | |||
⚫ | |||
unsigned short change_sign = 0; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
short i = 0,j = 0,k = 0; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
//Allocate memory to hold the subsequent digits in the form of a LUT |
//Allocate memory to hold the subsequent digits in the form of a LUT |
||
//For N = N, memory required for LUT = N(N+1)/2 |
|||
Index_Nos_ptr[i] = new int[N-i]; |
Index_Nos_ptr[i] = new int[N-i]; |
||
//Initialise the repetition value of each digit (Master and Local) |
//Initialise the repetition value of each digit (Master and Local) |
||
//Each digit repeats for (i-1)!, where 1 is the position of the digit |
//Each digit repeats for (i-1)!, where 1 is the position of the digit |
||
Line 151: | Line 152: | ||
//Initialise index values to access the arrays |
//Initialise index values to access the arrays |
||
Element_Num[i] = N-i-1; |
Element_Num[i] = N-i-1; |
||
//Initialise the arrays with the required digits |
//Initialise the arrays with the required digits |
||
for(j = 0;j < N-i;j++) |
for(j = 0;j < N-i;j++) |
||
*(Index_Nos_ptr[i] +j) = N-j-1; |
*(Index_Nos_ptr[i] +j) = N-j-1; |
||
} |
|||
⚫ | |||
} |
|||
⚫ | |||
std::cout << "Perm: ["; |
std::cout << "Perm: ["; |
||
for(i = 0;i < N;i++){ |
for(i = 0;i < N;i++){ |
||
//Print from MSD to LSD |
//Print from MSD to LSD |
||
std::cout << " " << *(Index_Nos_ptr[i] + Element_Num[i]); |
std::cout << " " << *(Index_Nos_ptr[i] + Element_Num[i]); |
||
//Decrement the repetition count for each digit |
//Decrement the repetition count for each digit |
||
if(--Digit_Rep_Local[i] <= 0){ |
if(--Digit_Rep_Local[i] <= 0){ |
||
//Refill the repitition factor |
//Refill the repitition factor |
||
Digit_Rep_Local[i] = Digit_Rep_Master[i]; |
Digit_Rep_Local[i] = Digit_Rep_Master[i]; |
||
//And the index to access the required digit is also 0... |
//And the index to access the required digit is also 0... |
||
if(Element_Num[i] <= 0 && i != 0){ |
if(Element_Num[i] <= 0 && i != 0){ |
||
//Reset the index |
//Reset the index |
||
Element_Num[i] = N-i-1; |
Element_Num[i] = N-i-1; |
||
//Update the numbers held in Index_Nos_ptr[] |
//Update the numbers held in Index_Nos_ptr[] |
||
for(j = 0,k = 0;j <= N-i;j++){ |
for(j = 0,k = 0;j <= N-i;j++){ |
||
//Exclude the preceeding digit (from the previous array) already printed. |
//Exclude the preceeding digit (from the previous array) already printed. |
||
if(j != Element_Num[i-1]){ |
if(j != Element_Num[i-1]){ |
||
*(Index_Nos_ptr[i]+k)= *(Index_Nos_ptr[i-1]+j); |
*(Index_Nos_ptr[i]+k)= *(Index_Nos_ptr[i-1]+j); |
||
k++; |
k++; |
||
Line 189: | Line 188: | ||
} |
} |
||
} |
} |
||
std::cout<<"] Sign: "<< sign <<"\n"; |
std::cout<<"] Sign: "<< sign <<"\n"; |
||
if(!(change_sign-- > 0)){ |
if(!(change_sign-- > 0)){ |
||
//Update the sign value. |
//Update the sign value. |
||
sign = -sign; |
sign = -sign; |
||
//Reset Toggle_Flag_Change_Condition |
|||
change_sign = 1; |
change_sign = 1; |
||
} |
} |
||
} |
} |
||
} |
} |
||
int |
int |
||
main() |
|||
{ |
{ |
||
Permutations(4); |
Permutations(4); |
||
getch(); |
getch(); |
||
return 0; |
return 0; |
||
⚫ | |||
} |
|||
{{out}} |
|||
⚫ | |||
Output: |
|||
<pre> |
<pre> |
||
Perm: [ 0 1 2 3] Sign: 1 |
Perm: [ 0 1 2 3] Sign: 1 |