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]]
On December 5, 2019 3:39:07 AM PST, "????????? ??????????" <dubrovvsskkyy at 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....> > [[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.
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
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, ????????? ?????????? <dubrovvsskkyy at 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 at 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.
>>>>> 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 at 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 at 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 at 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 at 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.