Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Combinations and Permutations "Rules"

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!


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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".


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

Multisets might need an entirely new app.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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...


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

Yes please, I love algorithms.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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,


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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?


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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 smile


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

mallikarjuns
Member
Registered: 2012-08-29
Posts: 1

Re: Combinations and Permutations "Rules"

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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

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


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

Hi MathsIsFun;

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

13560 is the correct answer.


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.

Offline

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

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Combinations and Permutations "Rules"

Ah, good then!


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

Have you implemented the removal of duplicates into the applet?


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.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations "Rules"

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}

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations "Rules"

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.


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.

Offline

Board footer

Powered by FluxBB