Mathematics desk
< October 11	<< Sep \| October \| Nov >>	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)[reply]

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)[reply]

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)[reply]

(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)[reply]

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)[reply]

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)[reply]