Permutation algorithm for list with duplcate numbers
Baljit
Could some one suggest me a good algorithm to generate a permutaion of
numbers some of which may be duplicates.
For a list of unique numbers there are n! permutations, but if some of
the numbers are duplcate then the permutaions will be less than this.
exmaple:
123: 123, 132, 213, 231, 312, 321.
112: 112, 121, 211
I'll appreciate if someone could even point to a relevant material or
a book.
Thanks
Baljit
Arturo Magidin
There are a number of ways of doing this. Almost any good book on
intro combinatorics will have this. I'm not sure if you want
permutations with repetitions, or ->combinations<- with repetitions,
but I suspect the latter.
In a permutation, the order matters, whereas your list seems to
indicate it does not, which would make it a combination.
For permutations, it is easy: if there are n possibilities for each of
the k spaces, then the total number of possible permutations with
repetitions is simply n^k.
For combinations, here is what you do:
Assume that you are trying to do combinations of {1,2,...,n}, taken k
at a time, with repetitions allowed.
We agree that we will list each combination in non-descending
order. Thus, we will write (1,1,1,3,4), but not (1,3,4,1,1), when
making a list of all such combinations.
Now we do a trick: instead of listing (c_1,...,c_k), where c_i is the
chosen number in the i-th position, we will list it as
(c_1,c_2+1,c_3+2,...,c_k+(k-1)) = (t_1,...,t_k)
(t_i is the "transformed" i-th entry).
Clearly, if we know this is what we are doing, then we can write any
combination this way, and we can interpret any such list as a
combination in a unique way.
The advantage of the latter list is that in such a list, there are
->no<- repetitions; that is, we must have t_1<...<t_k. Because
c_i<=c_{i+1}, so t_i = c_i+(i-1) <= c_{i+1}+(i-1) < c_{i+1}+i =
t_{i+1}.
Now, since c_i<=n, it follows that t_i<=n+(k-1). So each list
(t_1,...,t_k) is a list of integers, from 1 to n+k-1, without
repetitions, in ascending order. In other words, it is a combination,
->without repetition<-, of the number {1,2,...,n+k-1}, taken k at a
time.
We know the number of the latter is n+k-1 choose k, that is
(n+k-1)!
----------
k! (n-1)!
which gives you the number of choices.
Now, if we have an algorithm for listing combinations of r elements
taken s at a time without repetition, then the transformation
described above will list the combinations of n elements taken k at a
time with repetitions.
A standard algorithm for listing combinations without repetitions is
to start by listing the smallest possible choice in each entry, and
then moving the last entry by itself until you're done, then advancing
the last two, etc.
So, say you want to list all possible combinations with repetitions of
3 elements, taken 3 at a time (as you did above). n=3, k=3. Instead,
we list all possible combinations of 5=n+k-1 elements, taken 3=k at a
time. This is:
123, 124, 125, 134, 135, 145, 234, 235, 245, 345
Then apply the transformation described: in each entry, subtract 0
from the first choice, one from the second, two from the third; we
get:
111, 112, 113, 122, 123, 133, 222, 223, 233, 333,
the list all 10 possible combinations with repetitions of 3 elements,
taken 3 at a time.
(I usually think of this problem as "rolling k dice of n sides each;
how many distinct rolls are there?" The answer is n+k-1 choose k)
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Dirk Van de moortel
"Baljit" <baljit...@yahoo.com> wrote in message news:a84f5924.01120...@posting.google.com...
Here's a little example in VB, easily translated into any language.
Enjoy,
Dirk Vdm
' =====================================
Sub something()
Dim a(5) As Long
Dim d As Long
Dim perms As Long
d = 5
a(1) = 1: a(2) = 2: a(3) = 2: a(4) = 2: a(5) = 3
perms = 0
Do
perms = perms + 1
Print perms, a(1); a(2); a(3); a(4); a(5)
Loop While nextlong(d, a())
End Sub
' =====================================
Function nextlong(d As Long, a() As Long) As Boolean
' d = number of elements in array
' a() = array containing current permutation
' output:
' true if a next permutation is found and stored in a()
' false if no next permutation is found. a() is unchanged
Dim i As Long
Dim j As Long
Dim k As Long
Dim swap As Long
Dim s As Long ' smallest
Dim p As Long ' previous
Dim si As Long
For k = d - 1 To 1 Step -1
If a(k) < a(k + 1) Then
' first descendor a(k) found, swap this one with the smallest of
' the next ones that are greater than this descendor
s = a(k + 1)
si = k + 1
For i = k + 2 To d
If (a(i) > a(k)) And (a(i) < s) Then
s = a(i)
si = i
End If
Next
swap = a(si)
a(si) = a(k)
a(k) = swap
' bubble sort next ones (a quicksort can make this faster)
For i = k + 1 To d - 1
For j = i + 1 To d
If a(i) > a(j) Then
swap = a(i)
a(i) = a(j)
a(j) = swap
End If
Next
Next
nextlong = True ' got it
Exit Function
End If
If a(k) < s Then
s = a(k)
si = k
End If
p = a(k)
Next
' didn't find a smallest descendor: this must be the last permutation
nextlong = False
End Function
' =====================================
Al Dunbar
"Arturo Magidin" <mag...@math.berkeley.edu> wrote in message
news:9ull4d$1m9h$1...@agate.berkeley.edu...
> In article <a84f5924.01120...@posting.google.com>,
> Baljit <baljit...@yahoo.com> wrote:
> >Hi there,
> >
> >Could some one suggest me a good algorithm to generate a permutaion of
> >numbers some of which may be duplicates.
> >
> >For a list of unique numbers there are n! permutations, but if some of
> >the numbers are duplcate then the permutaions will be less than this.
> >
> >exmaple:
> >
> >123: 123, 132, 213, 231, 312, 321.
> >112: 112, 121, 211
> >
> >I'll appreciate if someone could even point to a relevant material or
> >a book.
>
> There are a number of ways of doing this. Almost any good book on
> intro combinatorics will have this. I'm not sure if you want
> permutations with repetitions, or ->combinations<- with repetitions,
> but I suspect the latter.
I'm no expert, but I believe the solution you provide below is to a problem
*different* from the one posted above.
The OP has a set of symbols that happens to include some duplicates. He
wants to display them in all possible orders, ignoring those arrangements
that are duplicates of those already output. Note that his line:
> >112: 112, 121, 211
is different from your line:
> 111, 112, 113, 122, 123, 133, 222, 223, 233, 333,
in that each element in his list (112,121,211) has exactly the same set of
digits shown in different orders, whereas this is not the case with your
elements.
<snip>
> 111, 112, 113, 122, 123, 133, 222, 223, 233, 333,
>
> the list all 10 possible combinations with repetitions of 3 elements,
> taken 3 at a time.
Exactly. The answer to a different problem.
> (I usually think of this problem as "rolling k dice of n sides each;
> how many distinct rolls are there?" The answer is n+k-1 choose k)
I'm not sure how I would think of the OP's problem, other than to say: "you
have a banana and two oranges: how many different ways can you display them
in a row"? Perhaps not as much appeal as the casino paradigm...
/Al
DIAMOND Mark R.
http://www.cs.sunysb.edu/~algorith/
which is run by Steven Skiena of SUNY whose web page is
http://www.cs.sunysb.edu/~skiena/
As you will see, the first site is an algorithm repository for all sorts of
combinatorial problems. Some of them are Skiena's own, but I believe that
many have been contributed or collected. A good beginning source is the book
%A Albert Nijenhuis
%A Herbert S. Wilf
%T Combinatorial Algorithms
%P Academic Press
By "beginning", I do not mean that it is a book for beginners. I mean that
almost all books on combinatorial algorithms since then have referred to
Nijenhuis & Wilf who themselves have selected relevant combinatorial
algorithms from people like Knuth.
--
Mark R. Diamond
Send email to server called psy dot uwa dot edu dot au and address to markd
http://www.psy.uwa.edu.au/user/markd
"Baljit" <baljit...@yahoo.com> wrote in message
news:a84f5924.01120...@posting.google.com...
Arturo Magidin
Al Dunbar <Al_D...@HoTMaiL.com> wrote:
>
>> In article <a84f5924.01120...@posting.google.com>,
>> Baljit <baljit...@yahoo.com> wrote:
>> >Could some one suggest me a good algorithm to generate a permutaion of
>> >numbers some of which may be duplicates.
[.snip.]
>I'm no expert, but I believe the solution you provide below is to a problem
>*different* from the one posted above.
Yeah, I think, on re-reading, that you're right. I interpreted as
"generate ->all<- permutations[combinations] of numbers some of which
may be dublicates".
Mike Hennebry
:numbers some of which may be duplicates.
:
:For a list of unique numbers there are n! permutations, but if some of
:the numbers are duplcate then the permutaions will be less than this.
:
:exmaple:
:
:123: 123, 132, 213, 231, 312, 321.
:112: 112, 121, 211
Start with something resembling an n! algorithm that finds places
for numbers, rather finding numbers for places.
Modify it to ensure that a duplicate is always placed after
its older brothers.
With good data structures the running time should be proportional
to the size of the answer.
--
Mike henn...@web.cs.ndsu.NoDak.edu
Iluvatar is the better part of Valar.
Lutz Tautenhahn
I implemented your code in a JavaScript page at
http://www.tu-chemnitz.de/~luta/plt/perm.html
but unfortunately it doesn't work correctly.
With your example 12223 I get the 11 permutations
12223 12232 12322 13222 21232 21322 22132
22231 22321 23221 32221
but I should get 20(=5!/3!) permutations.
Missing permutations are for instance:
31222 32122 32212
So I see 2 possibilities:
1. I didn't translate your code correctly
2. there's a bug in the code
Could you tell me, what you get in VB for this problem
instance, and I also would like to know what the line
p = a(k)
at the end of the function nextlong is good for.
Thanks,
Lutz Tautenhahn
"Dirk Van de moortel" <dirkvand...@ThankS-NO-SperM.hotmail.com> schrieb
im Newsbeitrag news:IbvP7.72835$XM4....@afrodite.telenet-ops.be...
Dirk Van de moortel
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in message news:9uoj1l$pum$1...@narses.hrz.tu-chemnitz.de...
> Hi Dirk,
> I implemented your code in a JavaScript page at
> http://www.tu-chemnitz.de/~luta/plt/perm.html
> but unfortunately it doesn't work correctly.
> With your example 12223 I get the 11 permutations
> 12223 12232 12322 13222 21232 21322 22132
> 22231 22321 23221 32221
> but I should get 20(=5!/3!) permutations.
> Missing permutations are for instance:
> 31222 32122 32212
> So I see 2 possibilities:
> 1. I didn't translate your code correctly
> 2. there's a bug in the code
> Could you tell me, what you get in VB for this problem
> instance, and I also would like to know what the line
> p = a(k)
> at the end of the function nextlong is good for.
>
> Thanks,
> Lutz Tautenhahn
It works for me: I get all 20 permutations 5! / (3!.1!.1!)
I've had a look at your java script.
You made a little error in the bubble sort:
{ for (j=i+1; j<d; j++)
should be:
{ for (j=i+1; j<=d; j++)
since in Vb it was:
For j = i + 1 To d
The p=a(k) is a left over from the "debugging" phase.
You can remove it, together with the Dim p.
Enjoy,
Dirk Vdm
Dirk Van de moortel
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in message news:9uoj1l$pum$1...@narses.hrz.tu-chemnitz.de...
> I implemented your code in a JavaScript page at
> http://www.tu-chemnitz.de/~luta/plt/perm.html
> but unfortunately it doesn't work correctly.
> With your example 12223 I get the 11 permutations
> 12223 12232 12322 13222 21232 21322 22132
> 22231 22321 23221 32221
> but I should get 20(=5!/3!) permutations.
> Missing permutations are for instance:
> 31222 32122 32212
> So I see 2 possibilities:
> 1. I didn't translate your code correctly
> 2. there's a bug in the code
> Could you tell me, what you get in VB for this problem
> instance, and I also would like to know what the line
> p = a(k)
> at the end of the function nextlong is good for.
>
> Thanks,
> Lutz Tautenhahn
Lutz (b.t.w. is this boy or girl?),
you seem to have corrected the little bugger :-)
Since I never programmed in Java, can I humbly ask you
something?
1) Could you please provide two check boxes on the form?
- one that controls whether all permutations are shown
or just the count,
- one that controls whether adjacent equals are allowed.
Could you also provide a text inputbox in which the initial
string can be put?. In the current example "12223"
I have posted the corresponding VB code on thread
"Permutation Counting Problem"
2) which environment do you use to create these java scripts?
Are you coding with a text editor or is there some kind of
'visual' environment to assist designing forms?
I'm asking this just to get a little kick start in java programming,
I hope it's not too much asked :-)
aTdHvAaNnKcSe,
Dirk
Lutz Tautenhahn
> Lutz (b.t.w. is this boy or girl?),
"Lutz" = "little Ludwig", many kings had the name "Ludwig",
following: "Lutz = little king" (q.e.d.)
> you seem to have corrected the little bugger :-)
>
> Since I never programmed in Java, can I humbly ask you
> something?
JavaScript is not Java, it is similar, but JavaScript is much easier.
JavaScript is pure script most directly included in a html page,
while Java is precompiled code in extern files which needs to be
included by using the object tag or the applet tag (you cannot
view and edit the sourcecode in the html page).
> 1) Could you please provide two check boxes on the form?
> - one that controls whether all permutations are shown
> or just the count,
> - one that controls whether adjacent equals are allowed.
> Could you also provide a text inputbox in which the initial
> string can be put?. In the current example "12223"
> I have posted the corresponding VB code on thread
> "Permutation Counting Problem"
Done.
> 2) which environment do you use to create these java scripts?
> Are you coding with a text editor or is there some kind of
> 'visual' environment to assist designing forms?
>
I use Notpad to code and IE 5.5 to view. I check the final web page
with Netscape 4.7, Netscape 6.1 and sometimes also Opera 5.
There are tools which assist in designing a html page, but I cannot
recommend to use it (for the use together with JavaScript). I made the
experience (with MS Frontpage), that such a tool can edit a web page
automatically when opening and closing a file (without asking for
confirmation) and in this way cause buggy code. When you prefer to see
the structure of your code by different colors, then you can use
"UltraEdit",
also the Undo can be done several times, what you will probably appreciate
in the beginning.
> I'm asking this just to get a little kick start in java programming,
JavaScript<>Java. All you need is a good documentation. I personally use and
recommend "SelfHTML" which is a very good doc, available for free at
http://www.teamone.de/
in german and since version 8 also in french.
> I hope it's not too much asked :-)
>
> aTdHvAaNnKcSe,
> Dirk
>
Good luck with programming in JavaScript!
Lutz
Dirk Van de moortel
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in message news:9uqlbn$rli$1...@narses.hrz.tu-chemnitz.de...
> Hello again,
>
> > Lutz (b.t.w. is this boy or girl?),
>
> "Lutz" = "little Ludwig", many kings had the name "Ludwig",
> following: "Lutz = little king" (q.e.d.)
Nice :-)
> > you seem to have corrected the little bugger :-)
> >
> > Since I never programmed in Java, can I humbly ask you
> > something?
>
> JavaScript is not Java, it is similar, but JavaScript is much easier.
> JavaScript is pure script most directly included in a html page,
> while Java is precompiled code in extern files which needs to be
> included by using the object tag or the applet tag (you cannot
> view and edit the sourcecode in the html page).
So apparently Java <==> Javascript like VB <==> VBscript
>
> > 1) Could you please provide two check boxes on the form?
> > - one that controls whether all permutations are shown
> > or just the count,
> > - one that controls whether adjacent equals are allowed.
> > Could you also provide a text inputbox in which the initial
> > string can be put?. In the current example "12223"
> > I have posted the corresponding VB code on thread
> > "Permutation Counting Problem"
>
> Done.
Thanks... now I know where to start (input, output and checkboxes).
> > 2) which environment do you use to create these java scripts?
> > Are you coding with a text editor or is there some kind of
> > 'visual' environment to assist designing forms?
> >
>
> I use Notpad to code and IE 5.5 to view. I check the final web page
> with Netscape 4.7, Netscape 6.1 and sometimes also Opera 5.
> There are tools which assist in designing a html page, but I cannot
> recommend to use it (for the use together with JavaScript). I made the
> experience (with MS Frontpage), that such a tool can edit a web page
> automatically when opening and closing a file (without asking for
> confirmation) and in this way cause buggy code. When you prefer to see
> the structure of your code by different colors, then you can use
> "UltraEdit",
> also the Undo can be done several times, what you will probably appreciate
> in the beginning.
I know, if I wouldn't have UltraEdit at my disposal I'd flatly
refuse to work. It is brilliant. I use it for writing perl, VBscript,
and just about everything that needs to be edited. I threw away
Not(e)pad a long time ago ;-)
For html I normally use FrontPage but I'll be on the look for
what it does with my scripts. Thanks for the warning.
>
> > I'm asking this just to get a little kick start in java programming,
>
> JavaScript<>Java. All you need is a good documentation. I personally use and
> recommend "SelfHTML" which is a very good doc, available for free at
> http://www.teamone.de/
> in german and since version 8 also in french.
At work I just found some CD-Roms packed with self-study courses.
Lots of Java & Javascript. I'm sure that will be enough to get started.
> > I hope it's not too much asked :-)
> >
> > aTdHvAaNnKcSe,
> > Dirk
> >
>
> Good luck with programming in JavaScript!
> Lutz
Thanks again,
Dirk