Complex combinatorics generation problem.

Software G'MIC
, ,
1

It looks like I have a very complex combinatorics problem again, I solved the other one. Right now, I need to generate N size of permutation with the restriction that every chars appear once. So, V(4,3) → 0012, 0021, 0102, 0112, 0120, 0121, …, 2210. You see where I’m going with this? I want to generate every possibilities that meets the criteria that is size of 4 with exactly 3 unique characters. len(V(n,k)) = fact(k)*S(n,k) where S is sterling number of second kind. That’s the amount of possibilities.

Right now, my failed code 
#@cli rep_rde_compsel_permutations: total_selection,number_of_item,_axis={x|y|z} : number_of_item_group,total_selection,_axis={x|y|z}
#@cli : Generates all possible permutations in which at least 1 item from each item group is select given N size.
#@cli : Author : Reptorian.
#@cli : Default values: '_axis=x'
+rep_rde_compsel_permutations:
skip ${3=x}

check isint($1,1)&&isint($2,1)&&inrange(('$3')[0],_'x',_'z',1,1)

number_of_item_groups,total_selection:=sort([${1-2}])
cutoff_point={$total_selection-$number_of_item_groups}

axis,length:=${-_rep_rde_lib_sterling_number_of_second_kind};[_'$3'-_'x',fact($number_of_item_groups)*sterling_number_of_second_kind($total_selection,$number_of_item_groups)]
{V=[1,1,1];V[$axis]=$length;V},$total_selection,>"begin(
		const n_ig=$number_of_item_groups;
		const dec_n_ig=n_ig-1;
		const last_indice=s-1;

		result=expr('x>$cutoff_point?x-$cutoff_point',s);
		counts=histogram(result,n_ig,0,n_ig);
		list_of_misses=vector(#n_ig);
		min_rp=last_indice;

		started=0;
	);
	started?(
		missings=0;last_missing=-1;swapped=0;
		t_counts=counts;

		if(x==5,print(result));

		for(rp=last_indice,rp>=0,--rp,
			last_v=result[rp];
			current_v=(last_v+1)%n_ig;
			is_current_missing=0;

			if(!--t_counts[last_v]&&rp,
				is_current_missing=1;
				++missings;
				last_missing=last_v;
			);

			--counts[last_v];
			++counts[result[rp]=current_v];

			if(is_current_missing&&missings==1,
				continue();
			);

			if(last_v<dec_n_ig,
				break();
			);
		);

		if(x==5,print(result));

		if(missings&&result[rp]!=last_missing;,
			--counts[result[last_indice]];
			++counts[result[last_indice]=last_missing];
		);
	):(
		started=1;
	);
	result;"

Currently, I was able to succeed up to 0201, and it skips 0210. I’m trying to keep it as optimal as I can. No deduplication, no set, no slicing list. Just “pure” array manipulation. All I know is that I’m pretty close, just no idea where to go from here.

2

Two ideas off the top of my head, they may be useless:

First, note that:

V(1,2) = empty
V(2,2) = 01, 10
V(3,2) = 001, 010, 011, 100, 101, 110

If you can find a pattern (which seems like it should be there), maybe there is a recursive definition for V(n, m) in terms of a simpler series (such as V(n-1, m)).

Second, is it feasible to brute-force the solution, and simply generate all possible sequences and then filter out those who don’t have all characters? It seems like only a small percentage of sequences will be discarded, so maybe this still qualifies as “as optimal as I can”.

3

The thing is I’d really like to avoid having to discard, and do it in place. And I think a solution that avoids discarding exists. All my other hard permutations problem had solutions where deduplication/discard could work, but it wasn’t necessary, and deduplication/discard wasn’t optimal in these.