Math Is Fun Forum

anna_gg

Member

Registered: 2012-01-10

Posts: 232

Re: 15 people in a row

I think the correct answer is 2291229 if my calculations are correct.

From all of the new formulas, the updated general formula for the answer in terms of n seats is:

The updated answer for n=15:

(about 51.19% of the total arrangements)

And we are as far as ever from an intuitive explanation

Last edited by anna_gg (2016-04-13 07:13:44)

Relentless

Member

Registered: 2015-12-15

Posts: 631

Re: 15 people in a row

Where does the huge disparity come from? What is missing? :S

If a whole lot more is missed in the adjacent combinations, then this calculator is getting really annoying xD

Please share what numbers you have so that I have a chance to derive general rules and figure out what is going on.

Last edited by Relentless (2016-04-13 15:20:44)

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Hi all;

Sorry I joined this so late, but it all looked too difficult. Anyway, I had some spare time the last couple of days (which I sure needed for this!) and have some answers.

I got the same end result as Anna: 2291229.

And here are my answers for the other 'levels':

I didn't do 13 & 14, because I went the slow way by using Excel (with some help from M and Notepad++), and the way I did it produced a huuuuge 1.4GB file that wasn't exactly motoring along for the 15 seats level! So 13 & 14 can wait...but looking at the progression I'd say they'd be around 331337 and 871303 respectively.

I tried coding the problem in M and nearly got there, so I might keep going with it...

Last edited by phrontister (2016-04-14 02:55:31)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 15 people in a row

Hi phrontister;

Your ansatz for 13 and 14 is pretty good (if your other values are correct).

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Relentless

Member

Registered: 2015-12-15

Posts: 631

Re: 15 people in a row

The values are correct. Once I switched to Excel everything matched (up to 12 seats so far). I will do the rest later and attempt general rules. Also keeping track of the numbers of adjacent and multiple adjacent combinations.

Good to finally have a reliable count.

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Hi all;

(if your other values are correct).

I hope my logic's ok.

Here's an example copy of my 3-column spreadsheet layout that shows what I did. I used the 5-seat option to keep the list to a manageable size.

Column B is M's copy/paste output of all 243 permutations for 5 seats.
Column A tests column B entries for either a "ww" or "mmm" content, and identifies, via incremental numbering, all valid seating arrangements.
Column C's first cell displays column A's last number.

The other seating numbers options use this same method.

EDIT: I've since changed column A's code, as evaluation for >10 seats was unacceptably slooooow. This means that the incremental numbering is no longer reported there - only "TRUE" or "FALSE". That also meant changing C1's code, but the totals remain unchanged.

Last edited by phrontister (2016-04-16 05:16:06)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Hi all;

So 13 & 14 can wait...but looking at the progression I'd say they'd be around 331337 and 871303 respectively.

Yes, those figures are correct, based on the method I've used for the other levels.

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 15 people in a row

Did you do it in M too?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Not yet. I've tried again, but still can't get past a major obstacle that's holding up progress. I may need your help with that, but I'll give it another go first.

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Got it!

I hadn't been able to work out how to use the Tuples output with its multiple comma-separated elements for each item in the list, but then succeeded by applying StringJoin to it (which I'd tried before but wasn't doing it properly). That then made it easier (for me) to test list items for "ww" or "mmm" content.

Btw, when I changed my Excel code (I mentioned that in post #31), that sped up the calcs enormously, and also reduced the file size from 1.4GB to 375MB. But M puts that to shame with its 13KB file size (including output)!

I would have saved hours if I'd spent just a few more minutes finding this instead of persevering with Excel (which I didn't mind doing, though).

The code calculates and prints all 15 levels in just under 30 seconds.

Last edited by phrontister (2016-04-17 01:46:41)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 15 people in a row

H phrontisteri;

So we can have 10 men at maximum and 8 women at maximum, if this is of any help

I am not getting how the code follows the above statement.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Hi Bobby,

My code covers the range of 1 to 15 seats, but I'll concentrate just on the 15 seats option, for which the code would be:

Count[StringFreeQ[Map[StringJoin,Tuples[{"m", "w", "k"},{15}]],{"ww","mmm"}],True]

There are 14348907 tuples, ranging from "mmmmmmmmmmmmmmm" through "wwwwwwwwwwwwwww" to "kkkkkkkkkkkkkkk".

StringJoin maps over Tuples to concatenate the comma-delimited tuples format to make it easier for me to work with.
StringFreeQ yields "False" for any items that contain either "ww" or "mmm", and "True" for any that don't.
Count yields the total number of "True" results...which is 2291229 (Anna's answer, and my Excel's).

So we can have 10 men at maximum and 8 women at maximum, if this is of any help

A search through the 14348907 tuples for the valid maximum arrangements you mentioned found 640 (ie, 5(2^7)) for 10 men and 128 (ie, 2^7) for 8 women.

Here's one example of each:

Men: {mmkmmwmmwmmkmmk}...position 1083351.
Women: {wmwmwkwkwmwkwmw}...position 5424635.

------------------------------------------------------------------------------------------------------------------
I haven't been able to work out how to create a list of the 2291229 valid arrangements. StringFreeQ only yields "True" or "False", and I can't get any more info from it than that. I've tried other functions (eg, Cases, DeleteCases, Select), but I must be doing it wrong. Not knowing much about patterns probably doesn't help.

So, the "search through the 14348907 tuples" I mentioned above was through Excel, which I trust as being as correct as M's results because they're identical for all 1 to 15 levels...and my M code is based on my Excel method. Also, I found the 1083351 and 5424635 positions with Notepad++ from a csv file I created with M of the 14348907 tuples.

Could you help me with creating the list in M of the 2291229 valid arrangements, please? I've tried and tried, but am totally stuck. Thanks!

So far I've got this to work:

EDIT: Found something on SE that works, and prints all 2291229 solutions:

Last edited by phrontister (2016-04-18 15:40:14)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 15 people in a row

Your code is a bit slower on my machine but it works.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

phrontister

Real Member

From: The Land of Tomorrow

Registered: 2009-07-12

Posts: 4,876

Re: 15 people in a row

Hi Bobby,

You may not have been able to keep up with all the edits to my previous post, where I said I've now worked out how to print the 2291229 solutions, but anyway, here are the positions of the two examples of maximum solutions I gave there, this time from the list of solutions instead of from the full tuples list.

Men: {mmkmmwmmwmmkmmk}...position 91303.
Women: {wmwmwkwkwmwkwmw}...position 893225.

Last edited by phrontister (2016-04-18 15:43:09)

---

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: 15 people in a row

Hi;

Okay, nice solution!

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Relentless

Member

Registered: 2015-12-15

Posts: 631

Re: 15 people in a row

For completeness;

The general formulas are somewhat elusive this time. I have only got:

For permutations with 2+ adjacent females:

A generating function for permutations with 3+ adjacent males:

With recursive formula:

And the previous wrong formulas

Last edited by Relentless (2016-04-19 14:05:48)