CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr
 MAIN INDEX SEARCHPOSTS WHO'S ONLINE LOG IN

Home: Perl Programming Help: Intermediate:
Re: [Laurent_R] how to skip redundant permutations?

 Print Thread

gevni
Novice

Nov 26, 2012, 6:49 AM

Post #1 of 13 (5757 views)
 Re: [Laurent_R] how to skip redundant permutations? Can't Post
I am looking for a function that will generate permutation on the basis of groups.
For example!

Set {A,B,C,D} normally has 4!= 24 different permutations

but if let say A,B belongs to 1 group and C,D belongs to other group 2. It will only generate 2 permutations and skip the other permutations.
The only two permutations that should be generated are

{A,B,C,D}
{C,D,A,B}

I am looking for generic solution so that i can scale it with more set elements.

Laurent_R
Veteran / Moderator

Nov 26, 2012, 10:44 AM

Post #2 of 13 (5748 views)
 Re: [gevni] how to skip redundant permutations? [In reply to] Can't Post
Hi, I understand in part what you want, but I am still puzzled.

Why couldn't you have ACBD? Or CBAD?

Suppose we say, for the sake of argument, that if two letters belong to the same group, we replace them by the first letter of the group, so we replace each occurrence of B by A and each occurrence of D by C.

Then, we start with the group ABCD, which gets translated into: AACC.

You could still have the following six permutations: AACC, ACAC, ACCA, CCAA, CACA, CAAC (if I did not forget any), not just two.

Again, this "translation" is just for the sake of discussion, it may be part of the final solution or may not be practical at all, or may not be what you need at all. For the time being, the only point in this "translation" is to understand better the requirement.

gevni
Novice

Nov 26, 2012, 11:12 AM

Post #3 of 13 (5746 views)
 Re: [Laurent_R] how to skip redundant permutations? [In reply to] Can't Post
I assume that if any element belongs to same group then order doesn't meter like in previous case

if {A,B,C,D} , Group 1= A,B && group 2= C,D
so any permutation order that only interchange intra group elements they are same, order within group doesn't meter and consider as a same order like
{A,B,C,D}
{A,B,D,C}
both are same.
Plus other thing i consider one group as one element
{1,2} so 2!=2

gevni
Novice

Nov 26, 2012, 11:22 AM

Post #4 of 13 (5745 views)
 Re: [gevni] how to skip redundant permutations? [In reply to] Can't Post
Means
{1,2}, {2,1}
Here
1=A,B
2= C,D
so resultant permutations are only
{A,B,C,D} and {C,D,A,B}

BillKSmith
Veteran

Nov 26, 2012, 12:23 PM

Post #5 of 13 (5740 views)
 Re: [gevni] how to skip redundant permutations? [In reply to] Can't Post
I looks to me like you want all permutations of the group numbers. Replace each group number with a list of its elements in arbitrary order.
Good Luck,
Bill

gevni
Novice

Nov 26, 2012, 12:30 PM

Post #6 of 13 (5738 views)
 Re: [BillKSmith] how to skip redundant permutations? [In reply to] Can't Post
Yes that is what i want. I have function where i submit the set and it will generate all permutations so if i only want these one and want to skip all other how my logic should be? Can any one show me in form of perl code?

Laurent_R
Veteran / Moderator

Nov 26, 2012, 2:09 PM

Post #7 of 13 (5733 views)
 Re: [gevni] how to skip redundant permutations? [In reply to] Can't Post
 In Reply To
Means
{1,2}, {2,1}
Here
1=A,B
2= C,D
so resultant permutations are only
{A,B,C,D} and {C,D,A,B}

No, as far as I understand your explanations, I have to disagree. Read again what I wrote in post #2, you have six possible permutations, not two.

If I summarize the letters with the group to which they belong, you have: {A,B,C,D} is 1122, and {C,D,A,B} is 2211.

{A,C,B,D} (or 1212), {A,C,D,B} (1221), {C,A,B,D} (2112) and {C,A,D,B} (2121) are in no case equivalent to your first two permutations, nor is any of them equivalent to any of the others. So I maintain that you have six possible permutations.

Or you have to explain an additional rule that you did not tell us about so far (or perhaps I missed some part of your explanation).

This is central to your task, so we really have to clarify this before we can go any further in trying to achieve what you want.

gevni
Novice

Nov 26, 2012, 2:45 PM

Post #8 of 13 (5729 views)
 Re: [Laurent_R] how to skip redundant permutations? [In reply to] Can't Post
{A,C,B,D} (or 1212), {A,C,D,B} (1221), {C,A,B,D} (2112) and {C,A,D,B} (2121) are not allowed because they separate group elements. 22 always remain adjacent (As they belongs to same group) and same as 11.
so there should only be {1122} {2211}

In my case initial set elements are always like

{1,1,2,2,2,3,3} initially 7! permutations

Here we have 3 groups with 2,3,2 elements inside that are sorted according to group value like group 1 elements come first then group 2 elements and then group 3 and so on.
During permutation we can't allow permutation option that separate one group elements like
{1,1,3,2,2,3,2} won't allowed
We only allow permutations like
{2221133}
{3322211}
in this case there are 3! permutations. I hope now you get what i want.

BillKSmith
Veteran

Nov 26, 2012, 8:53 PM

Post #9 of 13 (5713 views)
 Re: [gevni] how to skip redundant permutations? [In reply to] Can't Post
If the approach I described in post #5 meets your original requirement without any filtering, why are you even considering generating all possible permutations of all elements? Most of them would have to be declared invalid by the adjacency rule you explained to Laurent. Most of the rest would be eliminated because a redundant permutation has already been generated.

You did not say how many elements a group can have or how may groups you expect. The number of permutations which must be eliminated grows very rapidly. Consider five groups of three elements each. You want to keep only 5! of the 15! possible permutations. This notation hides the real size of the numbers. You would have to eliminate 1,307,674,367,880 of the 1,307,674,368,000, keeping only 120 permutations.

As you have already discovered, the filter is not simple. I cannot estimate the processing time for such a task, but I doubt that your boss would find it acceptable.
Good Luck,
Bill

Laurent_R
Veteran / Moderator

Nov 27, 2012, 4:36 AM

Post #10 of 13 (5696 views)
 Re: [BillKSmith] how to skip redundant permutations? [In reply to] Can't Post
I think you probably have to group items belonging to the same group together before you generate permutations.

You might have to do something similar to what is done in what is called Schwartzian Transform, i.e. first map your group of letters to a structure leading to a unique key for each group, then generate your permutation on the unique key, and then map back to the original value.

For example, if A and B belong to the first group, then map both {A,B} and {B,A} to 1 (1st group). Then use the unique key to figure out the permutations, and then map back to the original values.

BillKSmith
Veteran

Nov 27, 2012, 5:07 AM

Post #11 of 13 (5694 views)
 Re: [Laurent_R] how to skip redundant permutations? [In reply to] Can't Post
Laurent,

I started with the group numbers. The first step of your transformation would assign group numbers to each sequence of elements. From there on our approaches are the same.
Good Luck,
Bill

Laurent_R
Veteran / Moderator

Nov 27, 2012, 10:43 AM

Post #12 of 13 (5683 views)
 Re: [BillKSmith] how to skip redundant permutations? [In reply to] Can't Post
Bill, my answer was really to the OP, not to you, even though the post title might lead to think differently.

To the OP, building on my idea to transform the data before calculating the permutations and transform them again afterwards to get back the original format, you might do something like this.

Assume you have {1,1,2,2,2,3,3}.

You might transform it into {1_1, 2_2_2, 3_3}.
Then you just find all permutations of these three elements, which will give you six permutations. Then, in each permutation, you transform 1_1 back into {1,1}, and so on, so that if one of your permutations is {2_2_2, 1_1, 3_3), you just need to transform it back to: {2, 2, 2, 1, 1, 3, 3}.

This way, you only calculate the useful permutations, rather than calculating a large amount of permutations (7!, i.e. more than 5,000, in this case) and filtering them out afterwards

BillKSmith
Veteran

Nov 27, 2012, 12:26 PM

Post #13 of 13 (5677 views)
 Re: [Laurent_R] how to skip redundant permutations? [In reply to] Can't Post
Laurent,

We agree, but I do not think that either of us has convinced the OP of the folly in generating a possibly astronomical number of unwanted permutations and later filtering them out.
Good Luck,
Bill

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives