Iterate through 10-char arrangements with 5 Ts and 5 Fs

#1

My goal is to iterate through arrangements with 10 binary characters (each T or F) such that exactly 5 of them are Ts.

This is equivalent to generating a subset of 5 indices from 10 total indices; those 5 will dictate the location of the Ts.

I don’t want to iterate through all 2^{10} subsets, then see which ones have exactly 5 Ts. Instead, I only want to generate the \binom{10}{5} subsets/arrangements with the desired property.

How can I achieve this using:

  1. Recursion. I tried this, but it seems to iterate through all subsets, and it doesn’t work:
void gen_MY(int i=0, int t=0){ // i = current index, t = Ts so far
    if(t==5){
        keys.push_back(ANS);
        return;
    }
    if(i==10) return;
    ANS[i] = 'T'; gen_MY(i+1, t+1);
    ANS[i] = 'F'; gen_MY(i+1, t);
}
  1. Bitmasks. Is it possible to generate a bitset with exactly 5 1s? It is possible to iterate through all subsets:
for(int mask=0; mask < (1<<n); ++mask){
    int cnt = 0;
    for(int j=0; j<n; j++){
        if(mask & (1<<j)) cnt++;
    }
    if(cnt==5) keys.push_back(mask);
}

However, this isn’t what I want. Please read the sentences above for an explanation.

  1. Permutations. I know I can do this using next_permutation().
    MY = "FFFFFTTTTT";
    do{ keys.push_back(MY) }
    while(next_permutation(begin(MY), end(MY)));

I know how to implement permutation with recursion using a cnt map. However, I need to make sure the recursion doesn’t regard the 5 Fs as distinct or the 5 Ts as distinct. Can you please post your code for achieving permutation with recursion in this manner?

Please post a sample code for each of the 3 methods listed above. Thank you!

#2

cheese with python

from itertools import combinations

for inds in combinations(range(10), 5):
    print(inds)
#3

using permutations,

int cnt[2]; // 0 for F, 1 for T
string cur = "";
vector<string>ans;
void gen(int num) {
     if (num == 10) {
     	ans.push_back(cur);
     	return;
     }
     for (int i = 0; i < 2; ++i) if (cnt[i]) {
     	cnt[i]--, cur.push_back(i == 0 ? 'F' : 'T');
     	gen(num + 1); cur.pop_back(); cnt[i]++;
     }
}
int main() {
	cnt[0] = cnt[1] = 5;
	gen(0);
	assert((int) ans.size() == 252);
	// 252 is 10 choose 5
}
#4