Algorithm to Sort [closed]

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. Closed 10 years ago.

I have a list of numbers, for example: list=[10,50,开发者_如何学编程90,60]

I want to sorte the sum of any two elements. Along with their combinations.

For example: the output list should contain 10+50,10+90,10+60,50+90,50+60,90+60 (sorted in ascending).

i.e outputlist=[[60,10,50],[70,10,60]....

[similar to shake hand problems in permutations and combinations]

Can anyone give any hints?

---

Algorithms only since it's homework. I'd start with something simple. Based on your example, you don't want a full join of the list to itself, rather a list where element1 and element2 is identical to element2 and element1.

list = [10,50,90,60].
// newlist is an object containing first and second element.
newlist = [].
for i1 = 1 to list.size() - 1:
    for i2 = i1 + 1 to list.size():
        newlist.append (list[i1], list[i2]).
sort newlist based on sum of fields.

In other words, simply create a brand new list containing all the possibilities you need, then sort it based on the sum.

As to what types to use in Java, the original list can simply be an int array. I would opt for a independent class holding each combination (a simple class holding the two ints making up the combination would be sufficient) and an array to hold the lot.

The actual combinations array size can be pre-calculated, example combinations are:

size = 2 (ab    ) : (ab)             = 1
size = 3 (abc   ) : (ab,ac,
                        bc)          = 3
size = 4 (abcd  ) : (ab,ac,ad,
                        bc,bd,
                           cd)       = 6
size = 5 (abcde ) : (ab,ac,ad,ae,
                        bc,bd,be,
                           cd,ce,
                              de)    = 10
size = 6 (abcdef) : (ab,ac,ad,ae,af,
                        bc,cd,be,bf,
                           cd,ce,cf,
                              de,df,
                                 ef) = 15

so, where you have N elements, there are N-1 + N-2 + N-3 + ... + 1 combinations, which actually works out to be (N x N - N) / 2 or N x (N-1) / 2. And knowing that, you don't actually need any of the expandable collection classes (such as Vector), you can just use something like:

int[] list = {10,50,90,60};
int n = list.length;
myclass[] comb_array = new myclass[n*(n-1)/2];

Then once you've populated each element of that array using code similar to my pseudo-code above, Java provides public static void sort(Object[] a, Comparator c) which you can use to sort the actual array.

Alternatively (since this is homework), you may implement your own sort function, even something primitive like a bubble sort. I would never suggest that for production code since Java provides a rich tapestry of data types and methods, but it's probably acceptable for homework.

Update: Actually, I just noticed the homework tag was added by somebody else, not the OP. Now I'm fully aware that is most likely is homework but we can't be sure. And since SO is meant to be a place for answers, I'm going to provide an implementation below.

Fair warning: if you want to learn how to solve problems, start with what I've provided above and don't read below until you've spent at least a couple of days trying to figure it out. If you just want a solution to the problem then, by all means, feel free to use the code below as a starting point.

If you try to pass it off as your own work in a homework situation, you will fail because you would be supremely foolish to think your educators can't see this site as easily as you can. You deserve everything you get in that case and you'll get no sympathy from me.

I'm not going to bother providing a bubble-sort since that was only suitable for a homework question and, if that were the case, you wouldn't be reading down here, would you?

First of all, a double integer class DoubleInt.java. Not the most complicated one to understand and I haven't bothered with true encapsulation (private data with setters and getters) since it's only a helper class, and has no need of such luxuries :-)

public class DoubleInt {
    public int n1, n2;
    public DoubleInt (int i1, int i2) { n1 = i1; n2 = i2; }
}

Next, the actual code to do the combining and sorting, Abhishek.java:

// Need both these for sorting.

import java.util.Arrays;
import java.util.Comparator;

public class Abhishek implements Comparator<DoubleInt> {
    // The list of combinations.

    private DoubleInt[] dstList = null;

    // Inject a list to make the combinations out of.

    public void inject (int[] arr) {
        // This is from the algorithm given in the text above.

        dstList = new DoubleInt[arr.length * (arr.length - 1) / 2];
        for (int d = 0, s1 = 0; s1 < arr.length - 1; s1++)
            for (int s2 = s1 + 1; s2 < arr.length; s2++)
                dstList[d++]  = new DoubleInt(arr[s1], arr[s2]);
        Arrays.sort(dstList, this);
    }

    // Comparison function for Arrays.sort().

    public int compare (DoubleInt d1, DoubleInt d2) {
        if (d1.n1 + d1.n2 > d2.n1 + d2.n2) return 1;
        if (d1.n1 + d1.n2 < d2.n1 + d2.n2) return -1;
        return 0;
    }

    // Dump the array in index order for checking.

    public void dump() {
        for (int i = 0; i < dstList.length; i++) {
            System.out.println (i + ": " +
                // Note to educators: this
                // code plagiarized
                // from stackoverflow.com
                (dstList[i].n1 + dstList[i].n2) + " (" +
                dstList[i].n1 + "," + dstList[i].n2 + ")");
        }
    }

    // Test program to combine, sort and check.

    public static void main (String[] args) {
        abhishek a = new abhishek();
        a.inject (new int[] {10,50,90,60});
        a.dump();
    }
}

And the output from that is (formatted to look nicer):

0:  60 (10,50)
1:  70 (10,60)
2: 100 (10,90)
3: 110 (50,60)
4: 140 (50,90)
5: 150 (90,60)

which is sorted by the sum of the individual values. Changing the injection line to a.inject (new int[] {10,3,50,90,2,60,12,24,36,1}); results in:

 0:   3 ( 2, 1)          23:  60 (10,50)
 1:   4 ( 3, 1)          24:  60 (24,36)
 2:   5 ( 3, 2)          25:  61 (60, 1)
 3:  11 (10, 1)          26:  62 (50,12)
 4:  12 (10, 2)          27:  62 ( 2,60)
 5:  13 (10, 3)          28:  63 ( 3,60)
 6:  13 (12, 1)          29:  70 (10,60)
 7:  14 ( 2,12)          30:  72 (60,12)
 8:  15 ( 3,12)          31:  74 (50,24)
 9:  22 (10,12)          32:  84 (60,24)
10:  25 (24, 1)          33:  86 (50,36)
11:  26 ( 2,24)          34:  91 (90, 1)
12:  27 ( 3,24)          35:  92 (90, 2)
13:  34 (10,24)          36:  93 ( 3,90)
14:  36 (12,24)          37:  96 (60,36)
15:  37 (36, 1)          38: 100 (10,90)
16:  38 ( 2,36)          39: 102 (90,12)
17:  39 ( 3,36)          40: 110 (50,60)
18:  46 (10,36)          41: 114 (90,24)
19:  48 (12,36)          42: 126 (90,36)
20:  51 (50, 1)          43: 140 (50,90)
21:  52 (50, 2)          44: 150 (90,60)
22:  53 ( 3,50)          

where you can see the behavior of duplicate sums (13, 60 and 62) - the Java array sort is a stable one if I remember correctly.

---

First the basic choices: You can either first generate the permutations and then sort them, or you generate them in such a way that they are sorted from the beginning. If performance doesn't matter too much, I'd go with the first because it's easier.

Generating the permutations is straightforward, and then you can use Collections.sort to sort them.