You are not logged in.

- Topics: Active | Unanswered

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

Multisets might need an entirely new app.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

Yes please, I love algorithms.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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?

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

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

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

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

**MathsIsFun****Administrator**- Registered: 2005-01-21
- Posts: 7,626

Ah, good then!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline

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

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,688

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.****No great discovery was ever made without a bold guess. **

Offline