Re: [algogeeks] Re: DISTINCT Permutations ( Not Easy)
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf(%s\n, a);
for (j = i; j = n; j++)
{
if(a[i] != a[j])
{ swap(a[i], a[j]); //just check before swapping if
you are swapping different elements
//or not, if not then don't swap
permute(a, i+1, n);
swap([ai], a[j]);
}
}
}
On Sat, Jan 11, 2014 at 4:09 PM, bujji jajala jajalabu...@gmail.com wrote:
Hi Don,
Good one :) Nice to see different approaches for this problem.
-Thanks,
Bujji
On Fri, Jan 10, 2014 at 9:11 AM, Don dondod...@gmail.com wrote:
Sort the input string and remove duplicates, keeping a count of the number
of occurrences of each character.
They you can build the permutations easily.
For your example, you would start with
char *str = aba;
int len = strlen(str);
Which would be converted to
char *str ab;
int rep[N] = {2,1,0}; // The string contained 2 'a's and 1 'b'
char result[N];
Then call permute(str,rep,len)
void permute(char *str, int *rep, int len, int p=0)
{
if (plen)
{
for(int i = 0; str[i]; ++i)
if (rep[i])
{
result[p] = str[i];
--rep[i];
permute(str, rep, len,p+1);
++rep[i];
}
}
else printf(%s\n, result);
}
On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:
generate all possible DISTINCT permutations of a given string with some
possible repeated characters. Use as minimal memory as possible.
if given string contains n characters in total with m n distinct
characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m
= n
program should generate n! / ( n_1! * n_2! * * n_m! ) strings.
Ex:
aba is given string
Output:
aab
aba
baa
-Thanks,
Bujji
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
navneet singh gaur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: DISTINCT Permutations ( Not Easy)
formatting changes .
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf(%s\n, a);
for (j = i; j = n; j++)
{
if(a[i] != a[j]) check before swapping if you are
swapping different elements or not, if not then don't.
{ swap(a[i], a[j]);
permute(a, i+1, n);
swap([ai], a[j]);
}
}
}
-
On Wed, Mar 12, 2014 at 11:59 AM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf(%s\n, a);
for (j = i; j = n; j++)
{
if(a[i] != a[j])
{ swap(a[i], a[j]); //just check before swapping if
you are swapping different elements
//or not, if not then don't swap
permute(a, i+1, n);
swap([ai], a[j]);
}
}
}
On Sat, Jan 11, 2014 at 4:09 PM, bujji jajala jajalabu...@gmail.com wrote:
Hi Don,
Good one :) Nice to see different approaches for this problem.
-Thanks,
Bujji
On Fri, Jan 10, 2014 at 9:11 AM, Don dondod...@gmail.com wrote:
Sort the input string and remove duplicates, keeping a count of the number
of occurrences of each character.
They you can build the permutations easily.
For your example, you would start with
char *str = aba;
int len = strlen(str);
Which would be converted to
char *str ab;
int rep[N] = {2,1,0}; // The string contained 2 'a's and 1 'b'
char result[N];
Then call permute(str,rep,len)
void permute(char *str, int *rep, int len, int p=0)
{
if (plen)
{
for(int i = 0; str[i]; ++i)
if (rep[i])
{
result[p] = str[i];
--rep[i];
permute(str, rep, len,p+1);
++rep[i];
}
}
else printf(%s\n, result);
}
On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:
generate all possible DISTINCT permutations of a given string with some
possible repeated characters. Use as minimal memory as possible.
if given string contains n characters in total with m n distinct
characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m
= n
program should generate n! / ( n_1! * n_2! * * n_m! ) strings.
Ex:
aba is given string
Output:
aab
aba
baa
-Thanks,
Bujji
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
navneet singh gaur
--
navneet singh gaur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] variation of LIS problem
It can be solved in O(nlogn). Just start from the end and find
decreasing subsequence of size k. For example Eg
arr[]={5,2,1,10,9,30,8,55}, start from the end and put the subsequence
elements inside a different array.
Following concept can be used effectively in the same manner but we
have to just start from the end towards beginning to find decreasing
subsequence.
http://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
-
On Mon, Oct 28, 2013 at 11:22 PM, atul anand atul.87fri...@gmail.com wrote:
using idea mentioned in below link , we can solve this similar problem
in O(n^2*k).
http://stackoverflow.com/questions/12862077/number-of-increasing-strings-of-length-k
On 10/26/13, atul anand atul.87fri...@gmail.com wrote:
@saurabh : i did not get ur algo...can you please explain with an example
On 26 Oct 2013 08:21, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
if all the elements are positive then we can reverse the array and
multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since
it
gives the answer for all k=n with the minimum sum, this will be the
answer
multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja
rajkumar.cs...@gmail.comwrote:
I think O(nlogn) solution is possible for this problem. First find the
largest increasing subsequence in O(nlogn) time.
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
From this one u have LIS array M and parent array P. Now traverse
through
the array M and for all the length values = k , u can print the k
elements using Parent array P. I guess the step of printing the array
elements wont be greater than O(n logn).
So it is bounded by O(nlogn) . In the worst case it might go up to
O(n^2). But i am not sure of this.
On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote:
OK, i got now why you were using min-heap.
now consider this example :-
200,12,33,1,55,100
K=3
insert 200
12 200...cannot insert
33 200...cannot insert
.
.
.
100200 cannot insert
output : 200 (not lenght of k)
output should be : 33,55,100
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
Max-heap should not used in this case,
why min heap? -- this is because program has to decide the smallest
element
in k-group.
in your example if i consider k =3 than
insert 1
insert 2
insert 5
insert 10
size of heap ==4 so delete root of min- heap (which is 1),
insert 100
30 cant insert because temp = 100 and 30temp
insert 8 cant insert temp = 100 and 8temp
(500temp)size of heap ==4 so delete root of min-heap(which is 2)
insert 555
now if i check the heap elements
{5, 10, 100 , 555}
On Thu, Oct 24, 2013 at 11:25 PM, atul anand
atul.87fri...@gmail.comwrote:
in your updated algo , you should be using max-heap not min-heap.
check your algo for :-
1,2,5,10,100,30,8,555
let me know if it work fine.If it is working fine then i need more
clarity of your algo
On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
@Saurabh:
As per the question the elements of sub-sequence should be
increasing,
so the solution will be {5} and as per the program.
* but as written longest sub-sequence of k =2, so it should be
{2,3}
for
this case. (there should be backtrack in this case.)
@atul: increasing sub sequence is checked by condition, not by
Min-heap,
but min heap is used for storing the largest elements.
So it is preferable DS,
On Thu, Oct 24, 2013 at 8:35 PM, atul anand
atul.87fri...@gmail.com
wrote:
@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi
joshi10...@gmail.com
wrote:
@ Saurabh,
I have done a correction on algo
temp =0
loop n to a[]
if a[i]temp
if min-heap(root) a[i]
if min-heap(count)==k
delete root in min- heap
inseart a[i] in min - heap
As i have made the condition: min-heap, (condition size should
be
always
k) for this particular case.
And in the example {5,2,1,10,9,30,8,55} if K =3
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as
count
of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
and if k is 4
than
{5, 10, 30 , 55)
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
You must be mistaken in the definition of heaps, or maybe the
question,
look
