[R] Help to write the R-code, please

Martin Maechler m@ech|er @end|ng |rom @t@t@m@th@ethz@ch
Fri Dec 6 09:44:10 CET 2019


>>>>> 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:
     stvjc using 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, Александр Дубровский
    > <dubrovvsskkyy using 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 using 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 using 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.



More information about the R-help mailing list