生成含全部指定数字的n长字典序排列的代码问题排查

需求定义 #

V(n,k)需要生成所有长度为n的排列，每个排列必须包含0到k-1的所有数字，且按字典序排列，示例如下：

V(2,2) = { (0,1), (1,0) }
V(3,2) = { (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0) }
V(4,3) = { (0,0,1,2), (0,0,2,1), (0,1,0,2), ..., (2,2,1,0) }

所有排列均包含k个不同数字，仅元素频次存在差异，且严格遵循字典序。

问题描述 #

现有代码在测试n=4、k=3时，可正确生成至排列(0,2,0,1)，但后续跳过了(0,2,1,0)，直接生成(0,2,1,2)。经分析，原因是生成(0,2,0,1)后，代码将最后一位改为2、倒数第二位改为1，导致目标排列被遗漏。

现有代码 #

#@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));

        result[last_indice-1,2]!=[0,1]?(
            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(missings&&result[rp]!=last_missing;,
                --counts[result[last_indice]];
                ++counts[result[last_indice]=last_missing];
            );
        ):( 
            swap(result[last_indice-1],result[last_indice]);
        );
    ):( 
        started=1;
    );
    result;&quot;
_rep_rde_lib_sterling_number_of_second_kind:
u &quot;sterling_number_of_second_kind(_a,_b)=(
        ref(vector(##_a-_b+1,1),_arr);
        _max_q=_a-_b;
        _i_max_q=_max_q+1;
        for(_p=2,_p<=_b,++_p,
            for(_q=1,_q<_i_max_q,++_q,
                _arr[_q]+=_p*_arr[_q-1];
            );
        );
        _res=_arr[_max_q];
        unref(_arr);
        _res;
    );&quot;

内容的提问来源于stack exchange，提问作者Reptorian