>>>>> 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:
st...@channing.harvard.edu>; 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, Александр Дубровский
> <dubrovvssk...@gmail.com> 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]]
>>
>> ______________________________________________
>> R-help@r-project.org 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.
> ______________________________________________
> R-help@r-project.org 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.
______________________________________________
R-help@r-project.org 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.
