This article presents an algorithm for the problem of selecting combinations of elements.

## 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.

ExampleThe 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.

ExampleThe 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]$.

ExampleIf $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'$.

ExampleIf $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)$.

ExampleIf $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\}$.

ExampleFor 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.