>>>>> Richard O'Keefe

>>>>> on Fri, 6 Dec 2019 12:18:50 +1300 writes:

> This particular task is not a problem about R.

> It is a problem n combinatorics.

> Start with the obvious brute force algorithm

> (1) Let S be the union of all the sets

> (2) For each K in 0 .. |S|

> (3) Enumerate all |S| choose K subsets C of S

> (4) If C satisfies the condition, report it and stop

> (5) Report that there is no solution.

> There is a function 'combn' in the 'combinat' package that

> is perfectly suited to step 3.

combn() in "base R" (package 'utils') should probably suffice;

its help page [ help(combn) ] also mentions

Author(s):

Scott Chasalow wrote the original in 1994 for S; R package

‘combinat’ and documentation by Vince Carey <email:

[hidden email]>; small changes by the R core team,

notably to return an array in all cases of ‘simplify = TRUE’,

e.g., for ‘combn(5,5)’.

which may suggest that R's ("utils") version of combn() may even

be slightly improved

> I have not examined your outlined solution. Even if it is right,

> it pays to START by writing a crude obvious brute force

> algorithm like this so that you can test your test cases.

Definitely! First be *right*, only then think of being fast ..

Martin

> On Fri, 6 Dec 2019 at 03:14, Александр Дубровский

> <

[hidden email]> wrote:

>>

>> Task:

>> A family of sets of letters is given. Find K for which one can construct a

>> set consisting of K letters, each of them belonging to exactly K sets of a

>> given family.

>>

>> Possible solution:

>> For each letter, we will have a separate 'scoop', in which we will' put '

>> the letter. This can be done using array A of 255 elements. In this case,

>> the number of the 'scoop' corresponding to a letter is determined by the

>> letter code (it is known that any letter is encoded by some binary number

>> containing 8 digits - called bits; in Pascal, its code can be determined by

>> using the ord function). When viewing the sets, let's count how many times

>> each letter met. This is done as follows. When you meet a letter, increase

>> the contents of the corresponding array element by 1. The initial contents

>> of the array elements are 0. After viewing the letters of all sets,

>> elements a determine the number of corresponding letters, and therefore the

>> number of sets that have the corresponding letter (because in one set, all

>> elements are different!). Using similarly array B from 255 elements (more

>> need not, so as the desired the number of to on condition not exceeds

>> number of letters) count the number of units, twos and so on in array A.

>> Maximum significance index K, for which K=B[K] and will solution meet the

>> tasks.

>>

>> [[alternative HTML version deleted]]

>>

>> ______________________________________________

>>

[hidden email] mailing list -- To UNSUBSCRIBE and more, see

>>

https://stat.ethz.ch/mailman/listinfo/r-help >> PLEASE do read the posting guide

http://www.R-project.org/posting-guide.html >> and provide commented, minimal, self-contained, reproducible code.

> ______________________________________________

>

[hidden email] mailing list -- To UNSUBSCRIBE and more, see

>

https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide

http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code.

______________________________________________

[hidden email] mailing list -- To UNSUBSCRIBE and more, see

https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide

http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.