Let’s say I want to find the combination of letters at nth rank. How exactly I would do it? It’s easy to find the number of combinations via multiplying polynomials and then extracting the coefficient, but this isn’t about that.
Here’s a case: If you select only 7 of AABBCCCDDDD , and pick the 30th combination, it will be ABCDDDD.
Another case: If you select only 7 of AAAAAAAABBBCCCCCCCCCDDDD, and pick the 48th combination, it will be AACCCCD.
And we can see that the map of combinations looks like this:
You can note that it is indeed in lexicographic ordering. Each columns represent the chars. It also very easy to see that there’s a mathematical way of finding out the combination at nth rank.
Problem is that I have no direction to where.
The code - RDE Combinations Algorithm · GitHub
Or if you prefer to see it directly:
#@cli rep_rde_combinations: selected_count,item_0_count>=1,item_1_count>=1,...,_axis={x,y,z}
#@cli : Generates all possible combinations of repeated distinct elements of different counts, and the total number of elements is equal to the selected_count.
#@cli :
#@cli : Default values: '_axis=x'
+rep_rde_combinations:
check "isint($1,1)&&$#>1"
if isnum($-1)
items_counts=${2--1}
axis=0
else
check "inrange(_'$-1',_'x',_'z',1,1)"
items_counts=${2--2}
axis={_'$-1'-_'x'}
fi
check "items_counts=["$items_counts"];
( sum( isint(items_counts,1) ) == size(items_counts) ) && ($1 <= sum(items_counts) );"
number_of_possible_combinations=${_rep_rde_selected_comb_count\ $1,$items_counts}
if $number_of_possible_combinations>(1<<24) error exc_combin_size:$number_of_possible_combinations fi
out_dim={v=vector(#3,1);v[$axis]=$number_of_possible_combinations;v}
$out_dim,$1,>"begin(
items_count=["$items_counts"];
const number_of_sets_of_items=size(items_count);
const last_item_pos=number_of_sets_of_items-1;
result_vector=end_vector=vector(#$1);
const size_result_vector=size(result_vector);
const last_result_vector_pos=size_result_vector-1;
const start_compare_pos=last_result_vector_pos-1;
inserted_current_element_count=temp_pos=0;
repeat(size_result_vector,pos,
result_vector[pos]=temp_pos;
if(++inserted_current_element_count==items_count[temp_pos],
++temp_pos;
inserted_current_element_count=0;
);
);
pos=last_result_vector_pos;
temp_pos=last_item_pos;
inserted_current_element_count=0;
repeat(size_result_vector,
end_vector[pos--]=temp_pos;
if(++inserted_current_element_count==items_count[temp_pos],
--temp_pos;
inserted_current_element_count=0;
);
);
--result_vector[last_result_vector_pos];
);
if(++result_vector[last_result_vector_pos]==number_of_sets_of_items,
compare_pos=start_compare_pos;
do(
if(result_vector[compare_pos]!=end_vector[compare_pos],break(););
--compare_pos;
,compare_pos>=0);
selected_item=result_vector[compare_pos]+1;
inserted_current_element_count=0;
do(
result_vector[compare_pos++]=selected_item;
if(++inserted_current_element_count==items_count[selected_item],
++selected_item;
inserted_current_element_count=0;
);
,compare_pos<size_result_vector);
);
result_vector;"
