Combinations and Permutations "Rules"

MathsIsFun · 2012-01-30 15:16:31

I have been working on an upgrade to the Combinations and Permutations to allow "Rules" such as "not a and b together".

It is all explained below the calculator here:

Combinations and Permutations Calculator Test Version

You know when people post those interesting Comb/Perm questions with special conditions? Well, wouldn't it be nice if at least SOME of them could be handled by the calculator?

The "no" and "has" rules will help but we need more.

One rule I have thought about is "beside" (or "next"), but there are several variations.

Imagine you said "a is next to b":
* does that allow a on its own? (I think it should as you can use the "has 2,a,b" if you want to disallow it)
* does that include b,a as well as a,b? (maybe an option "both")
* does that include {a,x,y,z,b}? (because b "wraps around" to a) ... maybe a "circle" option for this one.

Anyway, all thoughts welcome. And test it out too!

bobbym · 2012-01-30 17:40:56

Hi MIF;

Working fine here. Those commands are useful and any other that you can implement.

The beside or next command is a step in the right direction. I think something like next ab,xx,cd which would be interpreted as an "a"followed by a "b" in the first two positions, then any two in the next two positions and "c" followed by a "d" in the next to last and last positions.

MathsIsFun · 2012-01-30 20:41:20

I could create a simple "pattern" command like "pattern,a,b,*,c,d"

Example: "pattern,*,a,*,c" which would be interpreted as: any number of items (including none?), then "a", then any items, ending in "c".

bobbym · 2012-01-30 20:58:24

That would be fine. Also, to finish it up the problem of multisets has to be dealt with.

MathsIsFun · 2012-01-30 23:16:17

Multisets might need an entirely new app.

bobbym · 2012-01-30 23:21:23

Hi MIF;

I generate listings of them on lots of combinatoric problems to test analytical answers. I think I can describe to you an algorithm from an ordinary permutation. When you are done with everything else and if you want to add them...

MathsIsFun · 2012-01-31 08:22:23

Yes please, I love algorithms.

bobbym · 2012-01-31 10:46:53

I can immediately provide an algorithm to list them all. To compute the number mathematically is more difficult because there is no formula known. I use generating functions when answering these so give me a little time to come up with a computerese solution.

MathsIsFun · 2012-01-31 12:45:18

Take your time. I also understand about the no-formula thing. The "rules" don't give formulas, just results.

We can also two-way a bit on the algorithm to get it right, so don't worry about being perfect.

bobbym · 2012-01-31 17:15:12

Hi MIF;

Would it be possible to remove the limitation that repeated elements can not be entered. The way it was originally.

http://www.mathisfunforum.com/viewtopic.php?id=3920

Post #8

I need to see the number of permutations it is computing,

MathsIsFun · 2012-01-31 18:02:24

Done! Use refresh, look for version 2.12a (bottom of app).

bobbym · 2012-01-31 23:50:12

Hi MIF;

Doing the order is important first.

Let's say someone enters t,o,o,t,h and puts in these parameters:

Types to choose from 5
Number chosen 2
Is order important? Yes
Is Repetition allowed? No

The output will be:

{t,o} {t,o} {t,t} {t,h} {o,t} {o,o} {o,t} {o,h} {o,t} {o,o} {o,t} {o,h} {t,o} {t,o} {t,t} {t,h} {h,t} {h,o} {h,o} {h,t}

To get the correct answer you only need to delete the duplicates.

{t,o} {t,t} {t,h} {o,t} {o,o} {o,h}{h,t} {h,o}

Which is correct. This has been verified for clandestine, mathematics, murmur, mississippi and collect.

Depending on your language, the task of deleting the duplicates can be difficult or easy. When this is done, I will test it against many more examples.

The field "Types to choose from" should be the same as the length of the input string, for tooth that is 5.

Should this method later on prove to be incomplete I have a better one that is sure to be correct but it requires more work. My feeling is that the above method will get the job done and is easiest.

MathsIsFun · 2012-02-01 11:30:38

So we ALLOW duplicates in the input, and remove duplicates in the result.

But removing duplicates from the result *might* be time consuming (checking every one against every other one in a list 1,000s of items long for example).

I don't think I can take advantage of them being in order, as, for example {t,o} appears in several positions. But there may be some clever duplicate discovery algorithm I haven't thought of.

But at least I know to only do duplicate removal if there are duplicates in input.

Is that reasoning correct?

bobbym · 2012-02-01 15:09:14

Hi

So we ALLOW duplicates in the input, and remove duplicates in the result.

This sort of post processing or processing at the end is wasteful and time consuming. There is just no way that I know of yet to efficiently prune them or not generate them at all.

You could sort the list of permutations, then the duplicates would be right next to each other. How slow will this be? I do not know, but I think the purpose of the app is to produce answers. A couple of seconds is not too much to ask when you need an answer.

Please do not get me wrong. I am not trying to sell you on this method. It is the jerks way of doing this. But it does solve the problem! To cover yourself you can say that I suggested it.

But at least I know to only do duplicate removal if there are duplicates in input.

Correct.

bobbym · 2012-02-03 22:05:04

Hi MIF;

How are you coming along with post #14? I have made no progress in finding a more efficient method. Even Knuth's new book does not cover it in a way that I can understand.

MathsIsFun · 2012-02-06 22:55:06

Doing fine now. It seems to work, but needs lots of testing.

Use refresh (look for v2.12b), try "t,o,o,t,h" etc.

Could you also try some normal combs/perms to see that I haven't accidentally injured other parts of the program

If we can get all this working and tested then I can post it as the main version

bobbym · 2012-02-06 22:58:01

Hi MathsIsFun;

What method did you use to generate them?

There is a problem on

Types to choose from 11
Number chosen 5
Is order important? Yes
Is Repetition allowed? No

m,a,t,h,e,m,a,t,i,c,s

depending on what output type you choose the box either comes up empty or gives the answer for 11 with 4 chosen.

mallikarjuns · 2012-08-29 19:00:15

Hi. Please post advanced permutations and combinations problems.
And my suggestion is please also write some intermediate advanced concepts in all chapters in math. And also increase difficulty level in practice questions for each chapter.

MathsIsFun · 2012-08-29 20:30:53

Thanks for the suggestions mallikarjuns!

And it looks like I missed a post from bobbym, ... when I try it I get:

Permutations without repetition (n=11, r=5)
Warning: your items have duplicates

List has 55440 entries.
After removal of duplicates in result, there are now 13560 entries.
{m,a,t,h,e} {m,a,t,h,m} {m,a,t,h,a} {m,a,t,h,t} {m,a,t,h,i} {m,a,t,h,c} {m,a,t,h,s} {m,a,t,e,h} {m,a,t,e,m} {m,a,t,e,a} {m,a,t,e,t} {m,a,t,e,i} {m,a,t,e,c} {m,a,t,e, ... etc

bobbym · 2012-08-29 21:12:51

Hi mallikarjuns;

There is a whole lot of advanced combinatoric problems here. Check my threads and see gAr's answers to them. Also follow juantherons posts and the solutions to them.

bobbym · 2012-08-29 21:18:13

Hi MathsIsFun;

After removal of duplicates in result, there are now 13560 entries.

13560 is the correct answer.

MathsIsFun · 2012-08-30 00:04:38

Ah, good then!

bobbym · 2012-08-30 00:09:02

Have you implemented the removal of duplicates into the applet?

anonimnystefy · 2012-08-30 00:20:57

Hi bobbym

If you open the applet, enter everything necessary and press the list button, you will see that, if there are any duplicates, the box says:

Combinations without repetition (n=5, r=2)
Warning: your items have duplicates

List has 10 entries.
After removal of duplicates in result, there are now 7 entries.
{a,a} {a,b} {a,c} {a,d} {b,c} {b,d} {c,d}

bobbym · 2012-08-30 05:23:20

Hi anonimnystefy;

Hmmm. Yes, it works well on that teeny, tiny problem but did you try the one I am using as
a test problem.

Math Is Fun Forum

#1 2012-01-30 15:16:31

Combinations and Permutations "Rules"

#2 2012-01-30 17:40:56

Re: Combinations and Permutations "Rules"

#3 2012-01-30 20:41:20

Re: Combinations and Permutations "Rules"

#4 2012-01-30 20:58:24

Re: Combinations and Permutations "Rules"

#5 2012-01-30 23:16:17

Re: Combinations and Permutations "Rules"

#6 2012-01-30 23:21:23

Re: Combinations and Permutations "Rules"

#7 2012-01-31 08:22:23

Re: Combinations and Permutations "Rules"

#8 2012-01-31 10:46:53

Re: Combinations and Permutations "Rules"

#9 2012-01-31 12:45:18

Re: Combinations and Permutations "Rules"

#10 2012-01-31 17:15:12

Re: Combinations and Permutations "Rules"

#11 2012-01-31 18:02:24

Re: Combinations and Permutations "Rules"

#12 2012-01-31 23:50:12

Re: Combinations and Permutations "Rules"

#13 2012-02-01 11:30:38

Re: Combinations and Permutations "Rules"

#14 2012-02-01 15:09:14

Re: Combinations and Permutations "Rules"

#15 2012-02-03 22:05:04

Re: Combinations and Permutations "Rules"

#16 2012-02-06 22:55:06

Re: Combinations and Permutations "Rules"

#17 2012-02-06 22:58:01

Re: Combinations and Permutations "Rules"

#18 2012-08-29 19:00:15

Re: Combinations and Permutations "Rules"

#19 2012-08-29 20:30:53

Re: Combinations and Permutations "Rules"

#20 2012-08-29 21:12:51

Re: Combinations and Permutations "Rules"

#21 2012-08-29 21:18:13

Re: Combinations and Permutations "Rules"

#22 2012-08-30 00:04:38

Re: Combinations and Permutations "Rules"

#23 2012-08-30 00:09:02

Re: Combinations and Permutations "Rules"

#24 2012-08-30 00:20:57

Re: Combinations and Permutations "Rules"

#25 2012-08-30 05:23:20

Re: Combinations and Permutations "Rules"

Board footer