Perl Guru Forums: Perl Programming Help: Intermediate: Re: [Laurent

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

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

gevni
Novice

Nov 26, 2012, 6:49 AM

Post #1 of 13 (6510 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 (6501 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 (6499 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 (6498 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 (6493 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 (6491 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 (6486 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 (6482 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 (6466 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 (6449 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 (6447 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 (6436 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 (6430 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

Search for (options)

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