Permutations by swapping: Difference between revisions

← Older editNewer edit →
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 fact(int size)
long
fact(int size)
{
{
int i;
int i;
Line 112: Line 112:


//function to display the permutations.
//function to display the permutations.
void
void Permutations(int N)
Permutations(int N)
{
{
//indicates sign
//indicates sign
short sign = 1;
short sign = 1;
⚫
//Tracks when to change sign.
unsigned short change_sign = 0;


⚫
//Tracks when to change sign.
⚫
//loop variables
short i = 0,j = 0,k = 0;
unsigned short change_sign = 0;
⚫
//iterations
⚫
long loops = fact(N);
⚫
//Array of pointers to hold the digits
⚫
int **Index_Nos_ptr = new int*[N];
⚫
//Repetition of each digit (Master copy)
⚫
int *Digit_Rep_Master = new int[N];
⚫
//Repetition of each digit (Local copy)
⚫
int *Digit_Rep_Local = new int[N];


⚫
//loop variables
⚫
//Index for Index_Nos_ptr
short i = 0,j = 0,k = 0;
⚫
int *Element_Num = new int[N];


⚫
//iterations
⚫
//Initialization
⚫
long loops = fact(N);
⚫
for(i = 0;i < N;i++){

⚫
//Array of pointers to hold the digits
⚫
int **Index_Nos_ptr = new int*[N];

⚫
//Repetition of each digit (Master copy)
⚫
int *Digit_Rep_Master = new int[N];

⚫
//Repetition of each digit (Local copy)
⚫
int *Digit_Rep_Local = new int[N];

⚫
//Index for Index_Nos_ptr
⚫
int *Element_Num = new int[N];


⚫
//Initialization
⚫
for(i = 0;i < N;i++){
//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
//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;
}
}


⚫
while(loops-- > 0){
}

⚫
while(loops-- > 0){
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 main()
int
main()
{
{
Permutations(4);
Permutations(4);
getch();
getch();
return 0;
return 0;
⚫
}</lang>
}
{{out}}
⚫
</lang>
Output:
<pre>
<pre>
Perm: [ 0 1 2 3] Sign: 1
Perm: [ 0 1 2 3] Sign: 1
Retrieved from "https://rosettacode.org/wiki/Permutations_by_swapping"