MthCombination/combinatoric.cpp at master · theSundayProgrammer/MthCombination · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122


#include <vector>
#include <algorithm>
#include <iterator>
using std::transform;
typedef std::vector<int> TCombo;
#include <stdio.h>
int factorial(int n)
//Factorial
{
    return n==0? 1: n*factorial(n-1);
}
int CC(int k, int n)
//Value of n-choose-k
{
    int val =1;
    for(int i=1; i<=k; ++i, --n)
    {
        val= val*n/i;
    }
    return val;
}
TCombo M_th_Combo(int M, int k,int n)
//Mth Combination
{
    using namespace std;
    if(k==0)
        return TCombo();
    else if (k==n)
    {
        TCombo ret;
        for (int i=0; i<n; ++i)
           ret.push_back(i);
        return ret;
    }
    else if (M < CC(k-1, n-1))
    {
        TCombo ret;
        TCombo sub = M_th_Combo(M, k-1,n-1);
        ret.push_back(0);
        transform(sub.begin(),sub.end(), std::back_inserter(ret), [] (int n) {return n+1;} );
        return ret;
    }
    else
    {
        TCombo ret = M_th_Combo(M-CC(k-1,n-1), k,n-1);
        transform(ret.begin(),ret.end(),ret.begin(),[] (int n) {return n+1;});
        return ret;
    }
}

TCombo M_th_Permut(int M, int k)
{
    if(k==0)
        return TCombo();
    int m0 =  M / (factorial(k-1));
    int m1 =  M % (factorial(k-1));
    TCombo ret;
    ret.push_back(m0);
    TCombo sub = M_th_Permut(m1, k-1);
    transform(sub.begin(),sub.end(), back_inserter(ret),
                [m0] (int n) { return n<m0 ? n : n+1;} );
    return ret;

}

int RankCombo(TCombo& combo, int k, int n)
{
    if (k==0 || k == n)
        return 0;
    else if(*combo.begin() == 0)
    {
        TCombo sub;
        transform(combo.begin() + 1, combo.end(), back_inserter(sub),
           [](int n) { return n-1;});
        return RankCombo(sub,k-1,n-1);
    }
    else
    {
        TCombo sub;
        transform(combo.begin(), combo.end(), back_inserter(sub),
           [](int n) { return n-1;});
        return CC(k-1,n-1) + RankCombo(sub, k, n-1);
    }
}

int RankPermut(TCombo& combo, int k)
{
    if (combo.size()==0)
        return 0;
    int m0 = combo[0];
    TCombo sub;
    transform(combo.begin() +1, combo.end(), back_inserter(sub),
           [m0](int n) {return n<m0 ? n : n-1;});
    return m0*factorial(k-1) + RankPermut(sub, k-1);
}

int main()
{
    int m=100,
        k=5,
        n=10;
    TCombo combo=M_th_Combo(m,k,n);
    std::for_each (combo.begin(), combo.end(),
    [](int k)
    {
        printf("%d ",k);
    });
    printf("\n%d %d %d", k, n, CC(k,n));

    printf("\n%d %d\n", m, RankCombo(combo,k,n));

    combo = M_th_Permut(m,n);
    std::for_each (combo.begin(), combo.end(),
    [](int k)
    {
        printf("%d ",k);
    });
    printf("\n%d %d\n", m, RankPermut(combo,n));
    printf("\nWow!\n");
}