Problem: Element Combination Using Marking Method

Problem Description

This article presents an algorithm for the problem of selecting combinations of elements $C(n, m)$.

Given a set $\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$ of size $n$ where $n>0$, extract $m$ elements $(0<m\leq n)$ as a combination and output all possible combination schemes.

Model Establishment

According to the combination formula, the number of ways to select $n$ elements from a set of $m$ elements is given by $\left( \begin{array}{c} n\\ m\\ \end{array} \right) =\frac{P_{n}^{m}}{P_m}=\frac{n!}{m!\left( n-m \right) !}$.

For a set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, an auxiliary marking sequence $A=\left[ 1,1,1,...,0,0,0 \right]$ is established to indicate whether the corresponding elements are included in the combination: $A[i]=1$ indicates that element $a_{i}$ is included in the combination, where $A[i]=0$ indicates that element $a_{i}$ is not included in the combination.

For example, for the set $S=\left\{ a_{1},a_{2},a_{3},a_{4} \right\}$ and the combination $C(4,2)$, all possible combinations are $\left\{ a_{1},a_{2} \right\}$, $\left\{ a_{1},a_{3} \right\}$, $\left\{ a_{1},a_{4} \right\}$, $\left\{ a_{2},a_{3} \right\}$, $\left\{ a_{2},a_{4} \right\}$, $\left\{ a_{3},a_{4} \right\}$. The corresponding auxiliary marking sequences are $\left\{ a_{1},a_{2} \right\}\rightarrow\left[ 1,1,0,0 \right]$, $\left\{ a_{1},a_{3} \right\}\rightarrow\left[ 1,0,1,0 \right]$, $\left\{ a_{1},a_{4} \right\}\rightarrow\left[ 1,0,0,1 \right]$, $\left\{ a_{2},a_{3} \right\}\rightarrow\left[ 0,1,1,0 \right]$, $\left\{ a_{2},a_{4} \right\}\rightarrow\left[ 0,1,0,1 \right]$, $\left\{ a_{3},a_{4} \right\}\rightarrow\left[ 0,0,1,1 \right]$.

The content expressed by the auxiliary marking sequence is the elements corresponding to the items marked as $1$ in the sequence, selected in the set and included in the combination. This auxiliary sequence facilitates the computation of combinations.

Auxiliary Sequence Transformation

The concept of the auxiliary marking sequence has been introduced above. Now, two special auxiliary marking sequences are defined.

Definition $A(S)$ represents the initial state auxiliary marking sequence for the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, denoted as $A(S)=\left[ a_{1},a_{2},...,a_{n},a_{n+1},a_{n+2},...,a_{m} \right]$, where $a_{i}=1(0<i\leq n)$ and $a_{j}=0(n+1 \leq j\leq m)$. It can be considered as the first combination method among all combination methods for the combination problem.

Example The sequence $A=[1,1,1,1,0,0,0,0,0]$ is the initial state.

The initial state auxiliary marking sequence has been introduced above. Now, the terminal state auxiliary marking sequence is introduced.

Definition For the combination problem of selecting $C(n, m)$ elements from the set $S=\left\{ a_{1},a_{2},a_{3},...,a_{n} \right\}$, the auxiliary marking sequence $A=[a_{1},a_{2},...,a_{n-m},...,a_{m}]$ is defined, where $a_{i}=0(0<i\leq n-m)$ and $a_{j}=1(n-m<j\leq m)$. This sequence is called the terminal state auxiliary marking sequence of this set.

Example The sequence $A=[0,0,0,0,1,1,1,1,1]$ is the terminal state.

Definition The operation function $Countf(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as the number of elements satisfying $a_{j}=1(0<j< i)$ in the subsequence $A=\left[ a_{1},a_{2},...,a_{i} \right]$.

Example If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Countf(A,i)$ for $i=7$. Since before $A[7]$ (excluding $A[7]$), there are a total of $3$ elements $1$ at $A[1]$, $A[4]$, and $A[6]$, so the value of $Countf(A,i)$ for $i=7$ is $3$.

Definition The operation function $Exch(A)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: find the smallest index $i$ satisfying $a_{i}=1$ and $a_{i+1}=0$, where $0<i\leq m-1$. Then exchange their values, i.e., set $a_{i}=0$ and $a_{i+1}=1$, obtaining the new sequence $A'$.

Example If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Exch(A)$. Obviously, find the minimum $i=1$, and get $a_{1}=1,a_{2}=0$. Swap them to get the new sequence $A'=Exch(A)=\left[ 0,1,0,1,0,1,1,1 \right]$

Definition The operation function $Movb(A,i)$ for the auxiliary marking sequence $A=\left[ a_{1},a_{2},...,a_{m} \right]$ is defined as follows: let $p=Countf(A,i)$ and $q=i-p-1$. Transform $A$ to get the new sequence $A'=[a_{1},a_{2},...,a_{p},a_{p+1},...,a_{i-1},a_{i},...,a_{m}]$, where $a_{i}=1(1<i\leq p)$ and $a_{j}=0(p<j<i)$.

Example If $A=\left[ 1,0,0,1,0,1,1,1 \right]$, find $Movb(A,i)$ for $i=5$. The new sequence is $A'=Movb(A,5)=\left[ 1,1,0,0,0,1,1,1 \right]$.

Definition Based on the auxiliary marking sequence $A$, output a combination scheme for the set $S$, called a restoration for sequence $A$. Denoted as $C(A)=\left\{ a_{i}\in S|A[i]=1 ,0<i\leq m \right\}$.

Example For the set $S=\left\{ a_{1},a_{2},a_{3},a_{4},a_{5},a_{6} \right\}$ and the sequence $A=[1,1,0,0,1,0]$, a restoration for $S$ with respect to $A$ is $\left\{ a_{1},a_{2},a_{5} \right\}$.

Algorithm Method

• Step 1: Obtain $A=A(S)$ from the set $S$, i.e., the initial state auxiliary marking sequence.
• Step 2: Output $C(A)$.
• Step 3: Check if the obtained auxiliary marking sequence is in the terminal state. If yes, terminate. If no, proceed to the next step.
• Step 4: Perform the transformation $A=Exch(Movb(A))$, and go back to Step 2.

With the above method, all combination schemes for the combination problem of selecting $C(n,m)$ elements from the set $S$ can be output.