[Solved] Combinatorial Design; Block Design

Talk about anything at all....
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

[Solved] Combinatorial Design; Block Design

Post by Silvabod »

Problem - Randomise numbers 1-22 six times, display in 5 groups of 4, with 2 over. (That's the easy bit - both randomise and display set up)
The hard bit - In the 6 lists, no two numbers may appear together more than once, and the twelve "2 over" numbers must all be different.

In everyday terms - 22 players on tour for 6 days, random team selection of 4 players in 5 teams, 2 reserves each day.
Qualification - no two players can be together more than once in the 6 days, and no player can be a reserve more than once.

Two questions (only one if the first answer is NO)
1/ is it mathematically possible ?
2/ How to code it ? My existing randomiser code is attached if that helps)
Attachments
22 random.ods
(25.96 KiB) Downloaded 427 times
Last edited by MrProgrammer on Sat Jan 22, 2022 6:53 pm, edited 2 times in total.
Reason: Tagged Solved as per OP's request
OpenOffice 4.1.5 on Windows 10
User avatar
Villeroy
Volunteer
Posts: 31264
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: Maths question - Is it possible ?

Post by Villeroy »

Sorry, I don't understand your spreadsheet. I made another one pulling 5 groups from 22 list entries. Duplicates are possible in theory but very unlikely.
Attachments
t105395.ods
(24.43 KiB) Downloaded 433 times
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04 with LibreOffice 6.0, latest OpenOffice and LibreOffice
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: Maths question - Is it possible ?

Post by Silvabod »

Sorry, your sheet effectively duplicates mine, using different coding. It creates a random selection for ONE day only - which mine also does, multiple times.
If your sheet were extended, there's still no comparison with 6 randomised lists, which is needed.
The questions were
1/ Is it mathematically possible (I won't bore you by repeating the limitations), and, if so,
2/ How to code ?
Appreciate your initial response and further contribution, perhaps.
OpenOffice 4.1.5 on Windows 10
User avatar
RusselB
Moderator
Posts: 6646
Joined: Fri Jan 03, 2014 7:31 am
Location: Sarnia, ON

Re: Maths question - Is it possible ?

Post by RusselB »

Is it mathematically possible? Yes.
How to code: Not as easy to answer, but I'll see what I can come up with after I'm home from work
OpenOffice 4.1.7, LibreOffice 7.0.1.2 on Windows 7 Pro, Ultimate & Windows 10 Home (2004)
If you believe your problem has been resolved, please go to your first post in this topic, click the Edit button and add [Solved] to the beginning of the Subject line.
User avatar
karolus
Volunteer
Posts: 1158
Joined: Sat Jul 02, 2011 9:47 am

Re: Maths question - Is it possible ?

Post by karolus »

Its easy peasy!

Code: Select all

from random import shuffle
a = list(range(1,23))
shuffle(a)
[a[n::4][:4] for n in range(5)] 

Code: Select all

[[1, 13, 4, 7],
 [2, 5, 21, 3],
 [17, 14, 22, 19],
 [10, 16, 8, 12],
 [13, 4, 7, 18]] 
AOO4, Libreoffice 6.1 on Rasbian OS (on ARM)
Libreoffice 7.4 on Debian 12 (Bookworm) (on RaspberryPI4)
Libreoffice 7.6 flatpak on Debian 12 (Bookworm) (on RaspberryPI4)
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: Maths question - Is it possible ?

Post by Lupp »

RusselB wrote:Is it mathematically possible? Yes.
What's the evidence you base this claim on?
karolus wrote:Its easy peasy!
one of the usual suspects wrote:Everything should be made as simple as possible, but not simpler.
What the questioner needs for the first day simply is a permutation of his list of participants. He then can group them as teams counting 5 times till 4. That's simple, and Calc can easily do the needed random shuffle by well-known means.
Concerning the second day we may try some alternative permutations, and check them for the mentioned conditions till we get one meeting them. We may even automate the needed checks.
There are 1124000727777610000000 (first 3 of the final zeroes not significant) 1124000727777607680000 permutations of 22 elements.
But stepping to the next day always very many are excluded due to the conditions regarding the grouping for the previous days.
Simple again: Every day excludes additional 3 of the participants as allowed team partners for every single one.
Looking just at one specific participant, and not regarding the "reserve" thing at all, we can state that the given conditions can't be met for an eighth day, because 21 (7*3) of the 21 original pals were already "used up".
Silvabod wrote: ...no two players can be together more than once in the 6 days...
Till now I haven't an answer to "Possible?" not to speak of the "How?" though the question was kind of a noise in my brain since I read it.

BTW: A few years ago the DFL (German Soccer League) commissioned a project concerning software for their game-plan development. See https://www.bundesliga.com/de/bundeslig ... 257823.jsp if interested.
A few known "usable" solutions are based on graph-designs ("graph" in the sense ot the related mathematical theory). There also is a pragmatical "English" concept for that special case.

I wouldn't announce a solution for both questions regarding my limited remaining time.
If it actually should be much simpler than I currently judge it, I'm intersted to learn.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: Maths question - Is it possible ?

Post by Silvabod »

karolus wrote:Its easy peasy!
Karolus, I'm an amateur at maths and Calc, but my English isn't bad. Surely, all this does is randomely sort 1 column ? I had already done this, multiple times by a different method yielding exactly the same result. Only then did I ask my questions.
The alternative "randomise" method is appreciated , unfortunately it doesn't answer either one of the two questions asked. Thanks anyway, for trying.
OpenOffice 4.1.5 on Windows 10
User avatar
RoryOF
Moderator
Posts: 34570
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

Re: Maths question - Is it possible ?

Post by RoryOF »

This boils down to a data selection problem with certain constraints controlling the selection. It is not a spreadsheet computation problem, although one can appreciate that the tabular form of a spreadsheet aids data input (names of players) and may also aid easy tabular display of the results, although such tabular displays can be easily and quickly arrived at in any programming language.

Were I to consider this problem (which I'm not going to do) I would be thinking of approaching it using Python to manipulate the sets of data merging from each constraint; there may be other programming languages more suited to the task.
Apache OpenOffice 4.1.15 on Xubuntu 22.04.4 LTS
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: Maths question - Is it possible ?

Post by Lupp »

Being an old man having just studied math for a while starting 58 years ago, I tried to solve the problem based on an actual mathematical approach. This was interesting and demanding (on my level), but only could give me some insight concerning probable genearalistations (number of participants, size of the teams, number of days...). Insofar I found rather simple but not too raw criteria telling that no solutions can exist under certain conditions.

Concerning the very specific case I could only verify that it is "at the edge". My analysis could neither exclude the possibility of a solution nor proove the existence of one - not to speak of showing a way to find all solutions or their number (if any).

As I already expected remembering slightly similar old poblems, I needed to guess and try, and ... - as it isn't uncommon with problems of constructive combinatorics.

If somebody has a good applicable theory, I'm interested.

Till then you may study and verify the solution contained in the attachment. It may need some time for its calculations. Some short comments you find inside.
To make it clear: The sheet didn't find the solution, but only helped with checks, and does the verification.
The randomization is next to trivial in the given case: Simply sort the participants once at the beginning, and identify them then by their numbers from 1 through 22. Concerning the structure I expect so few solutions that further randomization shouldn't make sense. Of course you can shuffle (randomize the order of) the days at the end if there are reasons.

Sorry. The file was a bit too large. It's somehow annoying in times of GiB traffic for every nonsense, to find the unchanged limit of 128KiB here.
I uploaded the sheet to: http://psilosoph.de/FreeOfficeForums/ao ... ions3a.ods
Of course, you need to permit macro execution (after having checked the code for the absence of malign parts).

BTW: To back my experimental steps by automated verifications, I needed a few user functions. That's not uncommon, and a life completely without programming is a bit dull anyway.
But: There is progress. If I want to use a function like TEXTJOIN(), I'm not happy with needing to search my custom-code archive whily knowing that LibreOfice has this function and many more implemented for years now. Users with edge-problems may consider to try a recent version of LibO in place of an old AOO.
However, I included code needed for AOO users to run the checks, and tested the sheet also with my portable AOO 4.1.7.
 Edit:  The "incomplete solution" contained in the range P8:U12 of the uploaded sheet contained 2 flaws:
Read "EBSP" in Q9 and "MRCH" in T11.
The final solution in P2:U6 should not be afflicted.  
 Edit:  Above mentioned flaws fixed meanwhile in the linked file.  
Last edited by Lupp on Sun Jun 06, 2021 1:03 pm, edited 2 times in total.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
User avatar
RoryOF
Moderator
Posts: 34570
Joined: Sat Jan 31, 2009 9:30 pm
Location: Ireland

Re: Maths question - Is it possible ?

Post by RoryOF »

I certainly recognise Lupp's expertise in mathematics - I admit to having forgotten almost all I ever learned!

At the back of my mind was an alternate approach, use of sets. A computer language - Prolog - (as far as I remember, not having needed to use it for 35+ years; there may be others) allows one to define various criteria for building and querying sets of data, and such set manipulation is handled by the underlying Prolog engine, without the labour of building mathematical constructs to represent and handle such manipulations.
Apache OpenOffice 4.1.15 on Xubuntu 22.04.4 LTS
User avatar
floris v
Volunteer
Posts: 4408
Joined: Wed Nov 28, 2007 1:21 pm
Location: Netherlands

Re: Maths question - Is it possible ?

Post by floris v »

That looks like the rules for "ringing the changes" - ringing the bells of a church in permutations with specific rules for the order of the permutations. From mutation N to mutation N=1 all positions have to be different. Typically, if you have 4 bells, you have to complete 24 permutations, in a fixed order, and it's a nice puzzle to figure it out. For 5 or more bells it becomes one hell of a job to do by hand.

I suggest that you use your programming skills in a language allowing recursion, and you will probably need backtracking.
OpenOffice 4.1.11 on Ubuntu; LibreOffice 6.4 on Linux Mint, LibreOffice 7.6.2.1 on Ubuntu
If your problem has been solved or your question has been answered, please edit the first post in this thread and add [Solved] to the title bar.
Nederlandstalig forum
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: Maths question - Is it possible ?

Post by Lupp »

I feel a bit tempted to offer an award for somebody finding a ready-made theory for the kind of problem, or for showhing me the means a (general-purpose) software or programming tool offers for the solution.

My "expertise" never was of much value, and it's long gone, but I dare to judge based on some experience that either the problem is "well-known" (based on thorough mathematical analysis, and to experts only, of course) or no straight-forward solution exists. Tell me if you find something.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
User avatar
MrProgrammer
Moderator
Posts: 4883
Joined: Fri Jun 04, 2010 7:57 pm
Location: Wisconsin, USA

Re: Maths question - Is it possible ?

Post by MrProgrammer »

Silvabod wrote:Randomise numbers 1-22 six times, display in 5 groups of 4, with 2 over. … In the 6 lists, no two numbers may appear together more than once, and the twelve "2 over" numbers must all be different.
This is a Calc forum. You have a problem in Combinatorics, especially Combinatorial Design and Block Design, branchs of mathematics, and need to look for your solution in a different forum. Once you have that solution, volunteers here may be able to help you with an implementation in Calc, depending on the algorithm. Some algorithms are impractical to implement in a spreadsheet. I will move this topic to the General Discussion forum.
RoryOF wrote:At the back of my mind was an alternate approach, use of sets. A computer language - Prolog - (as far as I remember, not having needed to use it for 35+ years; there may be others) allows one to define various criteria for building and querying sets of data, and such set manipulation is handled by the underlying Prolog engine, without the labour of building mathematical constructs to represent and handle such manipulations.
Agreed. I have not used Prolog myself, but am familar with the language's objective. The OP may be able to get help in a Prolog forum for a way to search for specific solutions, instead of studying the relevent mathematics which would give general solutions.
Lupp wrote:I feel a bit tempted to offer an award for somebody finding a ready-made theory for the kind of problem, or for showhing me the means a (general-purpose) software or programming tool offers for the solution.
I have also been interested in this as a mathematics problem but do not presently have the time to explore it. However if I achieve any progress I will be sure to let you know.
 Edit: The situation described here seems to be related to these articles in Wikipedia:
Kirkman's schoolgirl problem
Social golfer problem 
[Tutorial] Ten concepts that every Calc user should know
Mr. Programmer
AOO 4.1.7 Build 9800, MacOS 13.6.3, iMac Intel.   The locale for any menus or Calc formulas in my posts is English (USA).
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: Maths question - Is it possible ?

Post by Silvabod »

Lupp, Before I accidentally upset you, let me tell you that the data in area P2:U12 actually gives me a worktable. For which, our bowls team on tour thanks you (it was a genuine problem, not a theoretical exercise). I read both your post both here and on your worksheet (including the macro disclaimer) and downloaded it - was somewhat dismayed to find almost everything (95% or more) is showing #VALUE! but I DID find letter blocks placed in the empty cell area P2:U12 (Actual letters blocks only, not formulae). Nor did I find any macros.

You have used 22 letters instead of numbers. For my purpose, each letter (or number) actually represents a player. For reasons unknown you have combined all 4 team members into 1 group. I disassembled these groups into single blocks of 4, and visually verified that you have satisfied the brief - 22 players into 5 teams with 2 reserves daily, no player playing same player twice and no-one being substitute more than once. How you arrived at that data, I don't know - my maths is even older than yours (I'm nearly 79) and I find Calc difficult enough without venturing into even more sophisticated applications.

Many thanks, Problem solved!
OpenOffice 4.1.5 on Windows 10
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: [Solved] Maths question - Is it possible ?

Post by Lupp »

Concerning the "#VALUE!" thing: You didn't permit the execution of document-contained macros.
Well they are only of interest for those interested.

The solution was basically made "by brain" applying a few standard steps I used in practical combinatorics now and then. I often am not precise enough when checking conditions with the eye. Therefore I always tryied to verify solutions and optimizations using automatisms - and I like to write a little program now and then anyway. Calc can well support creative work of the kind if used without turning the expectations too high. "Let Calc create the solution" won*t work for me in the given case, and I also don't know more specific tools I would expect a solution of.

And once again: I suppose the problem is actually at the edge of allowing for a solution at all.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
User avatar
karolus
Volunteer
Posts: 1158
Joined: Sat Jul 02, 2011 9:47 am

Re: [Solved] Maths question - Is it possible ?

Post by karolus »

Hallo
me wrote:Its easy peasy
Sorry, I didnt recognize the whole task, but only the first day-step.
It has a solution, but we have to allow a Maximum of 2 Players in the same group on distinct Days.

Code: Select all

from itertools import combinations
from string import ascii_lowercase


def is_distinct(this, this_day_used):
    return not set(this).intersection(this_day_used)

def mostly_distinct( this, other):
    #we need to allow 2 Players in the same group on other days
    return len(set(this).intersection(other)) <= 2

def k_four(iterable,count=4):
    for combi in combinations(iterable, count):
        yield ''.join(combi)


def main():
    #lets express each `player` as one letter from `a` to `v`
    candidates = ascii_lowercase[:22]
    
    #prebuild a list of distinct reserve-players for 6 Days
    reserve = [candidates[n:n+2] for n in [0, 2, 4, 6, 8, 10]]
    
    out = []
    all_used = []
    
    for pair in reserve:
        day_used = []
        
        dayly = ''.join(sorted(set(candidates) - set(pair)))

        for combi in k_four(dayly):
            
            if (all(is_distinct(combi, used) for used in day_used)
                and all(mostly_distinct(combi, entry) for entry in all_used)):
                
                day_used.append(combi)

                if len(day_used) == 5:                    
                    all_used.extend(day_used)
                    day_used.append(pair)
        out.append(day_used)

    return out
                
                 
main()

Code: Select all

# the output:
[['cdef', 'ghij', 'klmn', 'opqr', 'stuv', 'ab'],
 ['abef', 'ghkl', 'ijmn', 'opst', 'qruv', 'cd'],
 ['abcd', 'ghmn', 'ijkl', 'opuv', 'qrst', 'ef'],
 ['abij', 'cdkl', 'efmn', 'oqsu', 'prtv', 'gh'],
 ['abgh', 'cdmn', 'efkl', 'oqtv', 'prsu', 'ij'],
 ['abmn', 'cdgh', 'efij', 'orsv', 'pqtu', 'kl']] 
AOO4, Libreoffice 6.1 on Rasbian OS (on ARM)
Libreoffice 7.4 on Debian 12 (Bookworm) (on RaspberryPI4)
Libreoffice 7.6 flatpak on Debian 12 (Bookworm) (on RaspberryPI4)
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

Lupp, apologies, when I opened it with macros, the #values were replaced with coherent data, as you said it would.
Think I mentioned, your sheet did come up with an answer (repeated 3 times) - multiple blocks of 4 letters including 2 "spares" which, when separated into single letters, gave me 30 team combinations and "spares". From this I can simply list the 22 bowlers, assign each a letter, and we have 5 teams and 2 reserves for each of the 6 days on tour.

It's also a simple matter to adjust for 21 bowlers (1 reserve) and 20 (no reserves). The 22nd letter is V, so delete it and use one of the daily reserve letters to replace every instance of V (similarly, for 20, delete/replace the U).
So, I have 3 possibilities for future annual tours if the number of bowlers is between 20 and 22. I use VLOOKUP to compare against the actual list of participants - problem solved!

It's a "once-a-year" event, now over 40 years old. The maximum number bowling at any one time is 24 (a bowling green is divided into 6 rinks) The maximum number of tourists we have had in the past is 28 (so there's been 4 reserves each day). Unfortunately the original organiser is no longer with us, we have no idea how he sorted the teams out !

I've studied your sheet. Whilst I do not understand the code, I think I understand some of the functionality. I thought I would try some changes. I noticed a minor thing - for some reason, you've used lower case " u " and " v ", I thought I would change to upper case. The sheet immediately started recalculating for some considerable time, so long that I stopped it, closed the process without saving.

Reopened the sheet, disabled the macro (to allow editing) added " W" and " X " in cells A24 and A25, then tried to change cell B2 to update the 22 to 24 in {=setofcombinations0(22;4)}. Error - "Can't change part of an array".
Problem - I can't find the extent of the array. If I select cell B2 and press "end" key it throws me across the spreadsheet to cell Y2. I'm fairly certain that the actual array is B2:E7316 as all these cells have the identical code. Seems I just don't have the skill to operate Calc at this level, I know nothing about arrays.

May I ask, please. Clearly you know far more than I, and it's your spreadsheet. Can you add letters W and X (perhaps one at a time) and update the various other codes, to see whether it works ? You will make a number of old people happy (we do have some youngsters, but the average age of our Club membership is over 70 - I'm 79 !).
Danke, Silvabod
OpenOffice 4.1.5 on Windows 10
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

 Edit:  
Karolus, many thanks for trying, but the output quoted completely fails the brief, multiple times.
The brief, in effect is " Letters a - v be sorted 6 times into 5 groups of 4, with 2 remnants. (so, 5 groups of 4 = 20, 2 "spares", 6 times).
Qualification - no two letters can be used twice in any group, and the 2 spare letters (reserves) also cannot be used twice. "
In the real world - it's a six day tour, 5 teams of 4 playing daily, with two reserves each day.
No player meets another player twice in a team during the 6 days, nor is he/she a reserve more than once.


Look below, in your quoted output.
In first column, AB is repeated 5 times, second column, GH repeats 4 times, 3rd column, KL repeats 3 times....and there's more ...

 ['cdef', 'ghij', 'klmn', 'opqr', 'stuv', 'ab'],
 ['abef', 'ghkl', 'ijmn', 'opst', 'qruv', 'cd'],
 ['abcd', 'ghmn', 'ijkl', 'opuv', 'qrst', 'ef'],
 ['abij', 'cdkl', 'efmn', 'oqsu', 'prtv', 'gh'],
 ['abgh', 'cdmn', 'efkl', 'oqtv', 'prsu', 'ij'],
 ['abmn', 'cdgh', 'efij', 'orsv', 'pqtu', 'kl'] end quote

It IS possible - no two letters in any block of 4 are together in another block, and the two reserves are also unique. (Thanks, Lupp!)
Day1   Day2   Day3   Day4   Day5   Day6
ABCD   AROL   VNGT   AJSH   AFKP   AEIU
EFGH   EBSV   ERKD   ENCL   EJOT   BFJN
IJKV   IFCT   IBOH   IRGP   INSD   CGKO
MNOP   MUGD   MFSL   MBKT   URCH   DHLP
QUST   QNKH   QJCP   VFOU   QBGL   QRVM

Daily reserve letters
R      J      U      D      M      S
L      P      A      Q      V      T
apologies if this screws up, copying tables from Calc sometimes results in disjointed tables.
Last edited by MrProgrammer on Mon Jun 07, 2021 6:19 pm, edited 1 time in total.
Reason: Added formatting tags -- MrProgrammer
OpenOffice 4.1.5 on Windows 10
User avatar
Villeroy
Volunteer
Posts: 31264
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: [Solved] Maths question - Is it possible ?

Post by Villeroy »

Have a look at this one.
Columns A is the random seed. Column B has arbitrary player names. You can sort by player names or randomly. For development I used the sort order "Player 01", "Player 02", "Player 03", etc.

Column E represents the first day with the same order of players as in the initial list.
Column F represents the second day where I referenced the previous day in a more or less systematic manner so the last reserve goes to group A and most of the others move into another group, so everybody sees different faces than yesterday.
I copied the same shift pattern from day 2 for days 3 to 6.
Attachments
players_t105395.ods
(28.06 KiB) Downloaded 445 times
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04 with LibreOffice 6.0, latest OpenOffice and LibreOffice
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

I've literally just closed my own - lost sleep thinking about it, got up at 4.15 am, been onscreen working till now (1.30pm) with a short break for egg on toast at around 9. Managed to (manually) find 38 blocks of 4 out of letters A - Z (38 unique quads), then reducing to 34 using letters 25 letters - I started at A, all the way down to O (by which time i was finding just one quad) so thought I probably had enough. Alas! - A yields 8 quads, and i can only use 6 (bowler bowls 6 days max) Then, there's the problem of sorting the unique blocks daily, showing 24 letters - think it's impossible.
Thank you for your sheet - I don't pretend to understand the code, but you've very nearly got the brief (22 = 20 active daily, 2 daily reserves, no-one bowls together twice, no-one is reserve twice). It's the reserves problem on your worksheet (which of course will impact the entire table), 4 bowlers are reserved twice on consecutive days (21, 4, 6 and 16). When updated, would it work for other numbers (23 would be 5 x 4 with 3 reserves, 24 would be 6 zx 4 with no reserves - I've actually bit the bullet and tried manually with 26 and 25 ? (6 x 4 with 2 and 1 reserve respctively) Do appreciate your continued interest - thanks! If my new manual worksheet containg lists and raw data is of any use, be happy to upload.
OpenOffice 4.1.5 on Windows 10
User avatar
Villeroy
Volunteer
Posts: 31264
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: [Solved] Maths question - Is it possible ?

Post by Villeroy »

My idea was to roll the dices only once for the first day and determine the other days by fumbling around with references. If one pattern turns out to be right, it will be right for any other sort order on day #1.

I'll attach a slightly modified sheet with 2 helpers. The green area tests if there are any duplicates in a day column. If so, the respective cells turn red. Any player name in cells L1:L4 highlight the same player in the main table. This reveals where people meet again in the same groups
Attachments
players_t105395_2.ods
(28.14 KiB) Downloaded 403 times
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04 with LibreOffice 6.0, latest OpenOffice and LibreOffice
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

Villeroy, sorry, same "reserve" problem, The download is Read-Only, which perhaps explains why there's absolutely NO functionality, with the exception of A2:A23 (all coded "RAND()" ). Pressing function key F9 recailculates ONLY Column A2:A23, and that's it - B2:B23 remain as you submitted, the output table D2:J23 remains static, and I don't pretend to understand the code in cells N2:S23 (assume this is the "helper" area). Despite the complex code, all 132 cells display "0".
So, the "reserve" problem remains (even worse now, 5 players affected) - nos 6, 3, 18, 13 and 4 are all reserved twice.
Perhaps it works if it wasn't"read-only" ?
Attached is a pic of one solution (there may be others) which fully addresses the brief (no two together at any time, and no repeat reserves)
Attachments
TOUR.JPG
OpenOffice 4.1.5 on Windows 10
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: [Solved] Maths question - Is it possible ?

Post by Lupp »

(I was absent from this thread and from the forum for a while now, and wouldn't read all the posts again, but:)
Silvabod wrote:t's also a simple matter to adjust for 21 bowlers (1 reserve) and 20 (no reserves).
You claim to have solutions for 5 teams, 4 players each, with no spare player at all or with exactly one, but as far as I can remember you never posted these solutions.

I would want to see them. We probably might learn something from them helping us to find ways to generalizations.

That's what I'm interested in beyond helping users of AOO/LibO. A one-case-only solution by software for a problem already solved by tinkering is of no use if not the starting point for a wider view.

How -if possible at all- to get at least one solution for p (players), t (per team), d (days with no reoccorring pair), and, of course k=INT(p/t) teams per day and p-k*t spare players none of them being "spare" on more than one day, is worth considerations like any unsolved problem is for a mathematician or a programmer.

To find all the correct solutions would be the next problem assigning itself to the community.

A ticklish question would then be how many equivalence-classes there are among the solutions, regarding two of them equivalent if they can be derived one from the other by (exlusively) permuting (A) the list of players, (B) the order of the teams for any given day, (C) the order of the days.

And whether or not all these classes are same size (by number of members).

You see? That's probably enough labor (trouble? fun?) for 5 master thesis in math or programming science.
Solve them all, and I will see to get a "PhD" for you.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
User avatar
Villeroy
Volunteer
Posts: 31264
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: [Solved] Maths question - Is it possible ?

Post by Villeroy »

If you would actually download my attachment, it wouldn't be read-only. If you just click the link and open the file without specifying any location on your PC, the file is opened for viewing because any changes would be lost anyway when you have no idea in which file the changes are saved.
So download the attachments.. Right-click the link and choose "Save As..." or some similar command (depends on your browser).

You found one solution to your problem all by yourself. I transfered your letters into my layout scheme.
Download the new attachment, click anywhere in the first column and hit one of the sort buttons in order to sort the players randomly. You may replace the letters in column B with actual player names.
Attachments
players_t105395_3.ods
(23.22 KiB) Downloaded 448 times
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04 with LibreOffice 6.0, latest OpenOffice and LibreOffice
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

Lupp wrote:(I was absent from this thread and from the forum for a while now, (( SILVABOD insert - ME TOO, JUST RETURNED, NOW MAIL CHECKING ))
Silvabod wrote:t's also a simple matter to adjust for 21 bowlers (1 reserve) and 20 (no reserves).
You claim to have solutions for 5 teams, 4 players each, with no spare player at all or with exactly one, but as far as I can remember you never posted these solutions.

I would want to see them.
From Silvabod - practical, not mathematical, solutions (it was a real-world query)

Lupp, the answer to this is your own solution for "22", some days ago. See my response above dated 9th June. I converted it into a table of Days and Teams/Reserves, which totally satisfies our needs.
Bear in mind my original question was practical - to create groups (teams) of 4 from a list of 22, plus 2 over (reserves) in such a way that no player was with another more than once in 6 days, and no player was a reserve more than once.
Your one and only solution fully satisfied those criteria, which I tabulated (and was the point where I marked this "SOLVED".

Again bear in mind it's an annual tour, so this will be used once a year. The simplest most practical answer to fulfilling the same criteria for 21 or 20 bowlers is this -
On the "22" table, remove the letter "V" (the 22nd letter) and replace every instance of "V" with the first of the two listed reserves each day. The daily sequence will be A to U, 21 letters, = 5 teams 1 reserve.
Similarly, to reduce to 20, delete both U and V (21st and 22nd letters), replacing each with the reserve letters each day (= 5 teams no reserves).
I recognise that both mathematically and code-wise, there would be many more unique solutions for below 22, but in practical terms, all we needed was one solution.
The actual names are drawn out of a hat each tour, which adds a further layer of randomisation (It's an annual tour, so if two people are drawn together a year later, that's the luck of the draw!
PS I've now been asked if I can get similar answers for 26, 25 24 and 23. Given your extensive research/calculations into 22, I think the answer is NO, but I'm manually working on an alpha list in Excel, manually checking (and doublechecking by listing unused letters (so first group is ABCD, second AEFG, third
AHIJ etc - the only unused letter in the A sequence is Z.
B sequence can only start BEHK, as the preceding letters CDFGIJ have already been used together in the A sequence.
Gets really difficult after L !
Incidentally, I posted my question "SOLVED" after your proof it could be done. For which, Many thanks from our Bowls Club.
OpenOffice 4.1.5 on Windows 10
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

Villeroy wrote: You found one solution to your problem all by yourself. I transfered your letters into my layout scheme.
Download the new attachment, click anywhere in the first column and hit one of the sort buttons in order to sort the players randomly.....
Credit where it's due - Lupp found the solution, all I did was refine its presentation.
Apols - Have now downloaded, saved onto HDD and opened it from there. Have modified slightly (Column widths only) so it displays/reads better.

I repeat most of what I said earlier (other than editing capability now that it's not Read-Only) the only functionality is Function key F9, which reacts on Column A only. All other columns remain as-is, no change.
No macros listed, nor any visible button(s). I'm colour-blind, I see no difference between colour in L1 and L2. L3 and L4 are different colours. So, cells L1 to L4 are coloured, but otherwise have no code, no content.

Area N2 :S23 is all same colour as L1/L2, visible content is numeric 0 in every cell, code virtually identical i.e
'=COUNTIF(E$2:E$23;E2)-1+STYLE(IF(CURRENT();"Bad";"Good")) is in cell E2, which I don't understand - if valid, would expect output either Bad or Good, not 0.

No trace of any buttons. ""click anywhere in the first column and hit one of the sort buttons in order to sort "" ... Clicked in Col A (first col) and in the absence of any on the worksheet, pressed F9, being the only sort button I know of. Nothing other than Col A recalculates.

Appreciate you attention, but am getting no-where. I already have a working solution so as stated several days ago, my problem is Solved. Thanks anyway
OpenOffice 4.1.5 on Windows 10
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: [Solved] Maths question - Is it possible ?

Post by Lupp »

@Silvabod:
Sorry. I just don't want to read a guide and try to play it through on my own at the moment.

I knew your solution "20 + 2 spare"was a slightly reformatted version of mine. You will remember that you claimed to have solutions (not strategies) for "20+0" and "20+1".

I simply asked you to post these solutions. If you want to add explanations which to read/use or not I can decide, that's ok for me. I just don't want to start into the next round of the pursuit by changing this to that and that to Quddlzwyth.
It's also ok, of course, if you refuse to do as I asked you. My free choice then concerning further participation in this thread.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

Lupp, apologies for my nationality! The German language is very structured, but English is not. For example, there's at least 3 solutions to stop a tap dripping - turn the water off at the main (no water = no drip = temporary solution), replace either the washer or the tap (both permanent solutions). All prevent the tap dripping (i.e. solve the problem) hence "solution" is the correctly used English word. No strategy involved.
Your answer (solution) to the problem of unique 20 + 2 was excellent. Later, I was asked for similar answers using different numbers, i.e. 20 + 1 and 20.

Rather than ask you to recalculate, it occured to me that if one (both) of the reserved letters were used to replace V (VU) in the table it would take very little time to answer (resolve) the new problems.
That's an obvious solution, to me. Strategy by definition implies a structured plan (such as a football game plan or a computer program) but the word "strategy" is rarely used in day-to-day English outside warfare, sport or long-term business planning scenarios.

If run through your program, reducing the totals to 21 or 20 would increase the probability of numerous different answers, however, the actual requirement is just one random table of players, no duplicates. So, my reduction(s) achieves the required result(s), i.e. solution(s), thanks to your original work. Thank you !
OpenOffice 4.1.5 on Windows 10
User avatar
Lupp
Volunteer
Posts: 3535
Joined: Sat May 31, 2014 7:05 pm
Location: München, Germany

Re: [Solved] Maths question - Is it possible ?

Post by Lupp »

Silvabod wrote:...reserved letters were used to replace V (VU) in the table it would take very little time to answer (resolve) the new problems...
I'm not a native speaker of any version of English, and my German surely also has flaws.
Anyway: What you describe is "how to get the solution" - what I badly called a "strategy". You may call it an instruction or a procedure or whatever you want, as long as you agree that it's not the "solution" itself.
A concrete solution must be a kind of table assigning all the players to one of the subdivisions (team or reserve) per day.
To proof the correctness of a solution may be possible by rather abstract considerations if you have a sufficiently powerful theory. In this case you haven't. You will need to actually do the replacements, and to check the results for their compliance with the preconditions.
I would like to see your results.
Sorry for my bad English.
On Windows 10: LibreOffice 24.2 (new numbering) and older versions, PortableOpenOffice 4.1.7 and older, StarOffice 5.2
---
Lupp from München
Silvabod
Posts: 18
Joined: Tue Jul 17, 2018 6:20 pm

Re: [Solved] Maths question - Is it possible ?

Post by Silvabod »

TOUR.JPG
Lupp, my PC is playing up, for some reason it refuses to load OpenOffice by any means (either directly, or via a saved worksheet). It's quite hot this afternoon. Maybe a reboot is needed, but takes too long, it's tea-time now. However, I do have a picture, and it's VERY easy to see the effect of my answer - doesn't need an actual worksheet.

You are correct in questioning my logic. I just followed it through. Just replacing the U and V with reserve letters doesn't guarantee uniqueness, I found one duplicate already after just one day ! Perhaps you would run it again, please, with just 20 and 21 characters ?

Thanks, Silvabod
OpenOffice 4.1.5 on Windows 10
Post Reply