wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sort array to get max concatinated value
        
(Message started by: birbal on Apr 11th, 2011, 7:48am)
Title: Sort array to get max concatinated value
Post by birbal on Apr 11th, 2011, 7:48am
Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141
Title: Re: Sort array to get max concatinated value
Post by pex on Apr 11th, 2011, 10:32am

on 04/11/11 at 07:48:50, birbal wrote:
Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

Looks like a greedy approach should work, using a lexicographic descending sort (with "end of number" coming before all digits).

Edit: hm, no, that would put 1 before 14. We could treat "end of number" as "last digit + 0.5", though.
Title: Re: Sort array to get max concatinated value
Post by birbal on Apr 11th, 2011, 9:58pm
I think for any two numbers A and B,
if (value(A.B) > value(B.A)), then A would come before B in the sorted and vice versa. But i cudnt really prove this :(
Title: Re: Sort array to get max concatinated value
Post by pex on Apr 11th, 2011, 10:55pm

on 04/11/11 at 21:58:54, birbal wrote:
I think for any two numbers A and B,
if (value(A.B) > value(B.A)), then A would come before B in the sorted and vice versa. But i cudnt really prove this :(

Yeah, that's the more understandable version of what I was trying to say. :) Think of how you would compare two very large integers, which you know have the same number of digits, by hand: you would first compare the most significant digits, break a tie using the second-most significant digits, etc. So in this problem, when you are constructing the number from left to right, the optimal thing to do at each step is to add the number that has the largest most significant digit, with the same tie-breaking rules.
Title: Re: Sort array to get max concatinated value
Post by birbal on Apr 12th, 2011, 1:05am

on 04/11/11 at 22:55:10, pex wrote:
Yeah, that's the more understandable version of what I was trying to say. :) Think of how you would compare two very large integers, which you know have the same number of digits, by hand: you would first compare the most significant digits, break a tie using the second-most significant digits, etc. So in this problem, when you are constructing the number from left to right, the optimal thing to do at each step is to add the number that has the largest most significant digit, with the same tie-breaking rules.


No i was trying to say something different. If the numbers have same number of digits, then it would be a simple integer comparison. But if number of digits are different in both the numbers, then we have to check the concatenated value.
For example
A = 1
B = 12
A.B = 112
B.A = 121
B.A > A.B, hence B comes before A in the sorted.
Title: Re: Sort array to get max concatinated value
Post by pex on Apr 12th, 2011, 1:19am
Yes. My remark about numbers of the same length was about comparing the results of different concatenation orders, sorry about the confusion.

If we apply the lexicographic sort I described above to your example, treating "end of number" as "last digit + 0.5", we would represent A = 1 as [1, 1.5] and B = 12 as [1, 2, 2.5]. First compare the first digits: 1=1, so we need to look at the next digits. 1.5<2, so B should come before A.
Title: Re: Sort array to get max concatinated value
Post by baskin on May 26th, 2011, 5:01am
How about this?
Compare each pair of integers using the concatenated string  value instead of normal integer comparison.


Code:
public static void main(String[] args)
{
int []a = new int[]{4, 94, 9, 14, 1};
Util.print(a);
SortUtil.quickSort(a, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return (o2.toString() + o1).compareTo(o1.toString() + o2);
}
});
Util.print(a);
}


o/p
4 94 9 14 1
9 94 4 14 1
Title: Re: Sort array to get max concatinated value
Post by birbal on Jun 2nd, 2011, 5:18am

on 05/26/11 at 05:01:53, baskin wrote:
How about this?
Compare each pair of integers using the concatenated string  value instead of normal integer comparison.


Code:
public static void main(String[] args)
{
int []a = new int[]{4, 94, 9, 14, 1};
Util.print(a);
SortUtil.quickSort(a, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return (o2.toString() + o1).compareTo(o1.toString() + o2);
}
});
Util.print(a);
}


o/p
4 94 9 14 1
9 94 4 14 1

isnt it similar to what i proposed in one of my posts ?
Title: Re: Sort array to get max concatinated value
Post by mmgc on Jun 3rd, 2011, 4:41am

on 06/02/11 at 05:18:25, birbal wrote:
isnt it similar to what i proposed in one of my posts ?


I think the beauty here is the use of quick sort to solve the problem.
Title: Re: Sort array to get max concatinated value
Post by towr on Jun 3rd, 2011, 8:47am
It's probably not an optimal way to do it though, because you operate on all characters, rather than on the few that are needed. You don't need to concatenate A and B unless one is the prefix of the other; in other cases plain (reverse) lexicographic order is sufficient.

I suspect a variant of bucket-sort might also work better than quick-sort, due to the nature of the problem. First sort on the first number, then within each group on the second, etc.
Title: Re: Sort array to get max concatinated value
Post by krishnav on Dec 25th, 2011, 6:28pm
@towr how would you sort between 9 & 94 and again between 1 & 12 using digit at a time sort?
Title: Re: Sort array to get max concatinated value
Post by towr on Dec 26th, 2011, 12:55am
It's a bucket sort, so strings with the same starting character are first put in the same bucket, but in the second round (as long as the second character is different) they'll be put in different buckets. You just have to be careful to have a bucket for strings that end at a given position; they're a bit of a special case.

So if we have 9,94,1,12
round 1:
bucket9 [9,94]
bucket1 [1,12]

round 2:
bucket9.e [9]
bucket9.4 [94]
bucket1.2 [12]
bucket1.e [1]
Title: Re: Sort array to get max concatinated value
Post by birbal on Dec 26th, 2011, 10:04am

on 12/26/11 at 00:55:16, towr wrote:
It's a bucket sort, so strings with the same starting character are first put in the same bucket, but in the second round (as long as the second character is different) they'll be put in different buckets. You just have to be careful to have a bucket for strings that end at a given position; they're a bit of a special case.

So if we have 9,94,1,12
round 1:
bucket9 [9,94]
bucket1 [1,12]

round 2:
bucket9.e [9]
bucket9.4 [94]
bucket1.2 [12]
bucket1.e [1]

I cudn't really understand what are you doing. Can you explain in a bit more detail, how would you arrange final buckets ?
Title: Re: Sort array to get max concatinated value
Post by krishnav on Dec 26th, 2011, 2:01pm
@towr I understood the bucket sort part...was curious how the empty digit would compare against a non-empty digit; we clearly cannot come up a fixed rule, such as empty's are greater than non-empty's or vice-versa.

because between 9 & 94, the empty (9) wins over 94.
and between 1 & 12, the non-empty (12) wins over 1.
Title: Re: Sort array to get max concatinated value
Post by kaka on Dec 26th, 2011, 5:35pm
While comparing empty value, assume it is equal to the left most digit
9 and 94 , assume we are comparing 99 and 94 and rate 9 over 94
1 and 12, assume we are comparing 11 and 12 and rate 12 over 1
Similarly for 832 and 83 , compare 838 and 832
Title: Why do you want to do it that way?
Post by carpinteyrojwf on Dec 26th, 2011, 6:46pm
Why do you want to do it that way?

spam link removed --SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board