CareerCup

/* Find all perm.
Notice that the permutations are nothing but a mapping between 
index sets - bitmaps into the list of items.
Observe, for a 3 member list {c : 3, b : 2 , a : 1 , '' :  0 } 
... 
Thus the problem is can be solved in 2 ways.
[1] Next higher permutation , when next is not there, increase number of digits
[2] Using the mthod of base 'k' numbers, when list is of size k - 1
where digits do not repeat. We implement  [2] here.
*/

def Permutations{
    def $$( list_of_items ){ // constructor 
      $.items = list_of_items 
      $.base = size( $.items ) + 1 
      assert( $.base - 1 == size( set( $.items) ), "Repeated items, I do not do those!" )
      $.cur_number = -1 // nothing 
    }
    def $next(){
       next_num = $.cur_number  
       while ( true ){
          next_num = next_num + 1
          base_change_string = str( next_num , $.base )
          //println( base_change_string )
          // can not use any integer that is having '0' as digit 
          continue ( '0' @ base_change_string )
          break ( size(base_change_string) > $.base )
          // if no digits repeated, then ok ?
          digits = set ( base_change_string.toCharArray )
          break ( size( digits) == size(base_change_string) )
       }
       break ( size(base_change_string) > $.base )
       $.cur_number = next_num
       // now map it back with the items 
       list ( base_change_string.toCharArray ) as { idx = int( $.o ) - 1 ; $.$.items[ idx ]  }
    }
}
p = new ( Permutations, [ 'a' ,'b' , 'c' ] )
for ( x : p ){
   println( x )
}

Why is BAA in the list but not BA

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Perm{
private:
vector<char> Parray;
int Count;
/*int factorial(int value){
int fact=1;
for(int i=1;i<=value;i++){
fact *= i;
}
return fact;
}*/

int findRforPos(int *p){
int max=0,tmp=0;
int r;
for(r=1;r<=Count;++r){
tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
if ((tmp+max)>=*p){
*p = *p - max;
return r;
}
max += tmp;
}
return Count;
}
public:
Perm( vector<char> array):Parray(array){
Count = Parray.size();
}

string findPos(int p){
string res;
int pos = p;
int r = findRforPos(&pos);
int sum=0;
//cout << r << endl;
while(r--){
sum=0;
for(int i=1;i<=Count;++i){
int tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
if((sum+tmp)>=pos){
pos = pos - sum;
res += Parray[i-1];
break;
}
sum+=tmp;
}
}
return res;
}

};

int main(){
vector<char> parray = {'a','b','c','d'};
int P;
cout << "Input Pos : ";
cin >> P;
Perm permobj(parray);
//for (int i =1;i<=P;i++){
cout << permobj.findPos(P) << endl;
//}
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Perm{
    private:
        vector<char> Parray;
        int Count;
        /*int factorial(int value){
            int fact=1;
            for(int i=1;i<=value;i++){
                fact *= i;
            }
            return fact;
        }*/
        
        int findRforPos(int *p){
            int max=0,tmp=0;
            int r;
            for(r=1;r<=Count;++r){
                tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
                if ((tmp+max)>=*p){
                    *p = *p - max;
                    return r;
                }
                max += tmp;
            }
            return Count;
        }
    public:
        Perm( vector<char> array):Parray(array){
            Count = Parray.size();
        }

        string findPos(int p){
            string res;
            int pos = p;
            int r = findRforPos(&pos);
            int sum=0;
            //cout << r << endl;
            while(r--){
                sum=0;
                for(int i=1;i<=Count;++i){
                    int tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
                    if((sum+tmp)>=pos){
                        pos = pos - sum;
                        res += Parray[i-1];
                        break;
                    }
                    sum+=tmp;
                }
            }
            return res;
        }

};

int main(){
    vector<char> parray = {'a','b','c','d'};
    int P;
    cout << "Input Pos : ";
    cin >> P;
    Perm permobj(parray);
    //for (int i =1;i<=P;i++){
        cout << permobj.findPos(P) << endl;
    //}
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Perm{
    private:
        vector<char> Parray;
        int Count;
        /*int factorial(int value){
            int fact=1;
            for(int i=1;i<=value;i++){
                fact *= i;
            }
            return fact;
        }*/
        
        int findRforPos(int *p){
            int max=0,tmp=0;
            int r;
            for(r=1;r<=Count;++r){
                tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
                if ((tmp+max)>=*p){
                    *p = *p - max;
                    return r;
                }
                max += tmp;
            }
            return Count;
        }
    public:
        Perm( vector<char> array):Parray(array){
            Count = Parray.size();
        }

        string findPos(int p){
            string res;
            int pos = p;
            int r = findRforPos(&pos);
            int sum=0;
            //cout << r << endl;
            while(r--){
                sum=0;
                for(int i=1;i<=Count;++i){
                    int tmp = pow(Count,r);//factorial(Count)/factorial(Count-r);
                    if((sum+tmp)>=pos){
                        pos = pos - sum;
                        res += Parray[i-1];
                        break;
                    }
                    sum+=tmp;
                }
            }
            return res;
        }

};

int main(){
    vector<char> parray = {'a','b','c','d'};
    int P;
    cout << "Input Pos : ";
    cin >> P;
    Perm permobj(parray);
    //for (int i =1;i<=P;i++){
        cout << permobj.findPos(P) << endl;
    //}
}