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

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++){
}
}
``````

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!

cheese with python

``````from itertools import combinations

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

using permutations,

``````int cnt; // 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 = cnt = 5;
gen(0);
assert((int) ans.size() == 252);
// 252 is 10 choose 5
}
``````