Generator(1)
A.First Edition
This is the first edition of my my Permutation Generator class. It is almost like a copy from the algorithm
from "Discrete Mathematics" into C++. I just do like a translating machine, cause I don't understand clearly
about what is doing there. Just to release the boredness of life. I am really feeling a low-morale without
coding. Later I add algorithm of generating combinations
B.Idea of program
1¡£ Basic idea:
What else can a thief talk about the thing that he stole from others?
2¡£ Program design:
I just make it a class and permutation is nothing but a sequence, so I give out the sequence index for the object to make a
"sequential permutation" (awkward?). I plan to give out my index array instead to handle the customer's object list.
Actually when customer get the index, he know how to do it. Therefore, I finish my job.
As for combination, you can see that each index of array is 1 for the element is in the set, or 0 for it is not. So, it is
simple. and do you feel cheated?
3¡£ Major function
A. void slotMachine();
I like the name.
4¡£ Further improvement£º
A. I was in a hurry as there is a final exam of Probability this evening and I just feel extremely
boring to be irresistable to do a little coding job.
#include <iostream> using namespace std; const int MaxNumber =100; class Generator { private: bool isCombination; int array[MaxNumber]; int length; void nextGenerator(); int nextDigit(); int findSmallest(int next); void swapIndex(int a, int b); void formTail(int next); void output(); void initialize(int number); protected: void doGenerator(); void doCombination(); public: Generator(int number =10, bool combination=false); void setLength(int number); int getLength() { return length;} void slotMachine(); }; int main() { Generator P(6); P.slotMachine(); return 0; } void Generator::doCombination() { int index =0; while (true) { while (array[index]) { array[index] = 0; index++; if (index==length) return; } array[index] = 1; output(); index =0; } } void Generator::doGenerator() { int next =0; int small =0; while ((next = nextDigit()) != -1) { small = findSmallest(next); swapIndex(next, small); formTail(next); output(); } } Generator::Generator(int number, bool combination) { setLength(number); isCombination = combination; initialize(number); } void Generator::output() { if (!isCombination) { cout<<"\nThis is the Permutation:\n"; } else { cout<<"\nThis is the Combination:\n"; } for (int i=0; i< length; i++) { cout<<array[i]<<(i==length - 1?";":","); } } void Generator::slotMachine() { output(); if (!isCombination) { doGenerator(); } else { doCombination(); } } void Generator::formTail(int next) { int start = next +1; int end = length -1; while (end > start) { swapIndex(start, end); start++; end--; } } void Generator::swapIndex(int a, int b) { int temp; temp = array[a]; array[a] = array[b]; array[b] = temp; } int Generator::findSmallest(int next) { int small = length -1; while (array[next]> array[small]) { small--; } return small; } void Generator::setLength(int number) { if (number>1) { length = number; } } int Generator::nextDigit() { int next = length -2; while (array[next]> array[next+1]) { next--; if (next<0) { return -1; } } return next; } void Generator::initialize(int number) { if (!isCombination) { for (int i=0; i< length; i++) { array[i]= i; } } else { for (int i=0; i< length; i++) { array[i]= 0; } } }
¡¡
This is the permutation: 0,1,2,3; This is the permutation: 0,1,3,2; This is the permutation: 0,2,1,3; This is the permutation: 0,2,3,1; This is the permutation: 0,3,1,2; This is the permutation: 0,3,2,1; This is the permutation: 1,0,2,3; This is the permutation: 1,0,3,2; This is the permutation: 1,2,0,3; This is the permutation: 1,2,3,0; This is the permutation: 1,3,0,2; This is the permutation: 1,3,2,0; This is the permutation: 2,0,1,3; This is the permutation: 2,0,3,1; This is the permutation: 2,1,0,3; This is the permutation: 2,1,3,0; This is the permutation: 2,3,0,1; This is the permutation: 2,3,1,0; This is the permutation: 3,0,1,2; This is the permutation: 3,0,2,1; This is the permutation: 3,1,0,2; This is the permutation: 3,1,2,0; This is the permutation: 3,2,0,1; This is the permutation: 3,2,1,0;
¡¡
This is the Combination:
0,0,0,0;
This is the Combination:
1,0,0,0;
This is the Combination:
0,1,0,0;
This is the Combination:
1,1,0,0;
This is the Combination:
0,0,1,0;
This is the Combination:
1,0,1,0;
This is the Combination:
0,1,1,0;
This is the Combination:
1,1,1,0;
This is the Combination:
0,0,0,1;
This is the Combination:
1,0,0,1;
This is the Combination:
0,1,0,1;
This is the Combination:
1,1,0,1;
This is the Combination:
0,0,1,1;
This is the Combination:
1,0,1,1;
This is the Combination:
0,1,1,1;
This is the Combination:
1,1,1,1;
¡¡