Help to write the R-code, please

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Help to write the R-code, please

Александр Дубровский
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.
Reply | Threaded
Open this post in threaded view
|

Re: Help to write the R-code, please

Jeff Newmiller


On December 5, 2019 3:39:07 AM PST, "Александр Дубровский" <[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.

...
>
> [[alternative HTML version deleted]]
>

This is a plain-text mailing list, meaning that some unspecified text version of your HTML-formatted messages will reach us which reduces our ability to understand you.

>______________________________________________

..

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

Do this. It warns you that this list is not for homework help, nor is it a do-my-work-for-me forum.
--
Sent from my phone. Please excuse my brevity.

______________________________________________
[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.
Reply | Threaded
Open this post in threaded view
|

Re: Help to write the R-code, please

Ivan Krylov
In reply to this post by Александр Дубровский
It might be easier to implement in R if you employ the base functions
that take arrays and operate on them as if they represented sets. See
the help() for "union", "intersect", "setdiff", "setequal" and the
operator "%in%".

--
Best regards,
Ivan

______________________________________________
[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.
Reply | Threaded
Open this post in threaded view
|

Re: Help to write the R-code, please

Richard O'Keefe-2
In reply to this post by Александр Дубровский
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.

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.

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.
Reply | Threaded
Open this post in threaded view
|

Re: Help to write the R-code, please

Martin Maechler
>>>>> 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-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.