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

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 Combination § Enumerating k-combinations. Given a set of sets ${\mathcal {T}}$ and an element $e$, let ${\mathcal {T}}\triangleleft \!\!\triangleleft ~e$ be defined as:

${\mathcal {T}}\triangleleft \!\!\triangleleft ~e=\{S\cup \{e\}|S\in {\mathcal {T}}\}.$ For example, $\{\{1,2\},\{1,3\},\{4\}\}\triangleleft \!\!\triangleleft ~5=\{\{1,2,5\},\{1,3,5\},\{4,5\}\}.$

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

$combs_{0}(S)=\{\emptyset \};$

$combs_{k{+}1}(\emptyset )=\emptyset ;$

$combs_{k{+}1}(S\cup \{e\})=(combs_{k}(S\setminus \{e\})\triangleleft \!\!\triangleleft ~e)\cup combs_{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 $combs_{k{+}1}(S)$ by $combs_{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(\emptyset )=\{\emptyset \};$

$subs(S\cup \{e\})=(subs(S\setminus \{e\})\triangleleft \!\!\triangleleft ~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)