Start by making a copy of the input array containing the sequence of
numbers. Sort the array. We'll call the copy A[n].
permute(int *a, int n, int k, int p=0)
{
if (p == k) output(a);
else
{
int tmp = a[p];
for(int i = p; i < n; ++i)
{
a[p] = a[i];
permute(a,n,p+1,k-1);
}
a[p] = tmp;
}
}
To generate permutations of the array, call permute(A, n, n);
Complexity is O(n!), which is the same as the size of the output.
Don
On Sep 22, 2:53 pm, kumar raja <[email protected]> wrote:
> (1) What is the efficient approach to generate permutations of a given
> sequence of numbers (may contain duplicates) in lexicographic order
>
> e.g. i/p: 5,1,6,1
> o/p:
>
> 1 1 5 6
> 1 1 6 5
> 1 5 1 6
> 1 5 6 1
> 1 6 1 5
> 1 6 5 1
> 5 1 1 6
> 5 1 6 1
> 5 6 1 1
> 6 1 1 5
> 6 1 5 1
> 6 5 1 1
>
> what is the time complexity of ur approach?/
>
> (2)What is the efficient approach to generate combinations of a given
> sequence of numbers (may contain duplicates) in lexicographic order
>
> e.g.
> i/p: {3,2 ,1,5,1,7}
>
> and k=2 (2-size subsets)
>
> o/p:
>
> 1 1
> 1 2
> 1 3
> 1 5
> 1 7
> 2 3
> 2 5
> 2 7
> 3 5
> 3 7
> 5 7 ( {5,7} is same as {7,5} because it is a selection).
>
> what is the time complexity of the algorithm??
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> [email protected]
> 7797137043.
> 09491690115.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
