Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 2014-11-05 15:00:20
- Martin01
- Guest
Permutation reverse?
Hi everyone
i need a help with permutation/combinations with letter a,b,c,d n=4 and r=4 no repetition
Permutations without repetition (n=4, r=4)
{a,b,c,d} {a,b,d,c} {a,c,b,d} {a,c,d,b} {a,d,b,c} {a,d,c,b} {b,a,c,d} {b,a,d,c} {b,c,a,d} {b,c,d,a} {b,d,a,c} {b,d,c,a} {c,a,b,d} {c,a,d,b} {c,b,a,d} {c,b,d,a} {c,d,a,b} {c,d,b,a} {d,a,b,c} {d,a,c,b} {d,b,a,c} {d,b,c,a} {d,c,a,b} {d,c,b,a}
the question is :
How can i know the 12th permutation {b,d,c,a} without calculate all 24 permutation ?
because sometime i can have many Millions permutations and i need to know how calculate directly the permutation i need ?
Tank You for your help
and sorry if my english is not very good im a french person!
Martin
#2 2014-11-05 15:50:51
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
Hi;
There is an algorithm to solve this problem but it is also a contest problem, is that why you want the 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
#3 2014-11-05 15:56:56
Re: Permutation reverse?
Can your algorithm calculate the nth permutation without calculating the n-1th?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#4 2014-11-05 16:27:23
- martin01
- Member
- Registered: 2014-11-05
- Posts: 2
Re: Permutation reverse?
HI, and Tank You for your support, i need to know this algorithm for my C++ project,
if you cannot send me the answer here for now, i can wait or you can send me a email
Tank You
Offline
#5 2014-11-05 21:02:14
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
Can your algorithm calculate the nth permutation without calculating the n-1th?
Yes it can.
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
#6 2014-11-05 21:49:40
Re: Permutation reverse?
I'll try coding it
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#7 2014-11-05 22:13:45
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
It will be a good exercise.
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
#8 2014-11-05 22:22:31
Re: Permutation reverse?
The contest is tomorrow.
Am I permitted to use recursion here?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#9 2014-11-05 22:33:21
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
What contest?
Use whatever you like.
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
#10 2014-11-05 22:50:25
Re: Permutation reverse?
Loop Way
factorial = lambda n: 1 if n==0 else reduce(lambda a,b: a*b, xrange(1,n+1))
def perm(string, n):
s = ''
while string != '':
i, n = n/factorial(len(string)-1), n%factorial(len(string)-1)
s += string[i]
string = string[:i] + string[i+1:]
return sThe Programming Contest. Didn't I tell you?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#11 2014-11-05 22:52:16
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
Which one?
What is the 100 000 000 permutation of 1234356789ABCD ?
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
#12 2014-11-05 22:55:51
Re: Permutation reverse?
12389A45D6B7C3
I was teaching a guy python, remember?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#13 2014-11-05 23:02:27
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
I am sorry, I forgot about that.
I do not know if that is correct because I have not looked up the algorithm in my notes yet.
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
#14 2014-11-05 23:07:22
Re: Permutation reverse?
Well, you can just check my algorithm and use it.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#15 2014-11-05 23:11:22
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
I could if you pseudocode it, I can never understand other people's code.
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 2014-11-05 23:25:32
Re: Permutation reverse?
Remember this conversation from #13963?
Pseudocode:
Input:
String as string
Permutation rank as n+1
Algorithm:
1. Initialise empty string s.
2. While string still has something, loop
{
1. Let l be the current length of string.
2. Attempt dividing n by (l-1)!. Set the remainder as n and the quotient as i.
3. To the extreme right of s, add the ith element of string.
4. Delete the ith element of string.
}
3. Output s
Last edited by Agnishom (2014-11-05 23:25:53)
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#17 2014-11-05 23:31:07
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Permutation reverse?
I remember it now. Thanks for the P code.
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 2014-11-06 01:09:27
- martin01
- Member
- Registered: 2014-11-05
- Posts: 2
Re: Permutation reverse?
Tank You for your time, i will try it today 
Last edited by martin01 (2014-11-06 05:18:36)
Offline
Pages: 1