Testwiki:Reference desk/Archives/Mathematics/2021 October 12

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < October 11 ! width="25%" align="center"|<< Sep | October | Nov >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 12

Combinatorial algorithms

For a given natural number k, and a given set S, is there an algorithm - generating all subsets of S, each of which is - a k-combination - i.e. containing k elements of S?

I suspect Wikipedia does not give any information about that algorithm (which I guess is recursive) 84.228.239.160 (talk) 11:10, 12 October 2021 (UTC)

Of course there is one; see Template:Section link. Given a set of sets $𝒯$ and an element $e$, let $𝒯◃◃e$ be defined as:

$𝒯◃◃e=\{S\cup \{e\}|S\in 𝒯\}.$ For example, $\{\{1,2\},\{1,3\},\{4\}\}◃◃5=\{\{1,2,5\},\{1,3,5\},\{4,5\}\}.$

Let $comb{s}_k(S)$ denote the set of $k$-combinations of elements of $S$. The following is an explicit recursive function definition.

$comb{s}_0(S)=\{\mathrm{\varnothing }\};$

$comb{s}_{k+1}(\mathrm{\varnothing })=\mathrm{\varnothing };$

$comb{s}_{k+1}(S\cup \{e\})=(comb{s}_k(S\setminus \{e\})◃◃e)\cup comb{s}_{k+1}(S\setminus \{e\}).$

--Lambiam 12:23, 12 October 2021 (UTC)

Thanks. If k is not given in advance, and I want to generate all subsets of a given set S, should your algorithm be used for generating all k-combinations of S for every (whole non-negative) k not larger than the number of elements of S? or there is a simpler algorithm for that? 84.228.239.160 (talk) 13:07, 12 October 2021 (UTC)

(I've made a correction to the last clause by replacing $comb{s}_{k+1}(S)$ by $comb{s}_{k+1}(S\setminus \{e\}),$ which avoids an infinite loop in case $e\in S.$) To get all subsets, just ignore the subscripts controlling the size, as follows:

$subs(\mathrm{\varnothing })=\{\mathrm{\varnothing }\};$

$subs(S\cup \{e\})=(subs(S\setminus \{e\})◃◃e)\cup subs(S\setminus \{e\}).$

--Lambiam 19:03, 12 October 2021 (UTC)

Here is a Next Subset algorithm (in Fortran, I think) - you can call it until you get all subsets. When I need to get all subsets, I often do it like counting from 0 to 2ⁿ in binary. For instance when it gets to 1100₂, take the third and fourth members of the set. Also, see several implementations at Rosetta code. Bubba73 ^{You talkin' to me?} 04:27, 13 October 2021 (UTC)

OP's comment: Thank y'all. I thought the algorithm should be recursive, but after reviewing all the suggestions you have put forward, I used the common idea behind all of them - to build a non-recursive algorithm which I found most comfortable for me. 84.228.239.160 (talk) (UTC) 19:56, 13 October 2021 (UTC)