Алгоритм сортировки

Question

У меня есть список номеров, например: list=[10,50,90,60]

Я хочу SORTE сумму любых двух элементов. Наряду с их комбинациями.

Например: выходной список должен содержать 10 + 50,10 + 90,10 + 60,50 + 90,50 + 60,90 + 60 (отсортировано по возрастанию).
outputlist = т.е. [[60,10,50], [70,10,60] ....

[похоже трясти проблемы рук в перестановок и комбинаций]

Может кто-нибудь дать какие-то намеки?

Answer 1

Алгоритмы только с домашней работы. Я бы начал с чего-то простого. На основе вашего примера вы не хотите, чтобы полное объединение списка было само собой, а список, в котором элементы element1 и element2 идентичны элементам2 и элементу1.

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. 

Другими словами, просто создайте новый список, содержащий все возможности, которые вам нужны, а затем отсортируйте его на основе суммы.

Что касается типов, используемых в Java, исходный список может быть просто массивом int. Я бы выбрал независимый класс, держащий каждую комбинацию (простой класс с двумя int с составлением комбинации был бы достаточным) и массив для хранения партии.

Фактический размер комбинации массива могут быть предварительно вычислены, примеры комбинаций:

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 

так, где у вас есть N элементы, есть N-1 + N-2 + N-3 + ... + 1 комбинации, которые на самом деле работает, чтобы быть (N x N - N)/2 или N x (N-1)/2. И зная, что вы на самом деле не необходимости любой из расширяемых классов коллекций (такие как Vector), вы можете просто использовать что-то вроде:

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

Тогда, как только вы населен каждый элемент этого массива с помощью код, похожий на мой псевдо-код выше, Java предоставляет public static void sort(Object[] a, Comparator c), который вы можете использовать для сортировки фактического массива.

В качестве альтернативы (поскольку это домашнее задание), вы можете реализовать свою собственную функцию сортировки, даже что-то примитивное, как вид пузыря. Я бы никогда не предположить, что для производственного кода, так как Java обеспечивает богатый гобелен типов данных и методов, но это, вероятно, приемлемо для домашней работы.

Обновление: На самом деле, я только что заметил, что тег домашней работы был добавлен кем-то другим, а не OP. Теперь я полностью понимаю, что, скорее всего, - домашнее задание, но мы не можем быть уверены. И так как SO предназначено для того, чтобы быть местом для ответов, я собираюсь предоставить реализацию ниже.

Справедливое предупреждение: если вы хотите, чтобы узнать, как решить проблемы, начните с того, что я Приведенную выше и не прочитать ниже, пока вы не потратили по крайней мере несколько дней, пытаясь понять его вне. Если вы просто хотите решить проблему, то, во что бы то ни стало, не стесняйтесь использовать приведенный ниже код в качестве отправной точки.

Если вы попытаетесь передать это как свою работу в домашней ситуации, вы получите , потому что вы были бы в высшей степени глупы, чтобы думать, что ваши преподаватели не могут видеть этот сайт так легко, как вы можете. В этом случае вы заслуживаете всего, что у вас есть, и со мной не будет сочувствия.

Я не собираюсь беспокоиться о предоставлении пузырьковой сортировки, поскольку это было подходящим только для домашнего задания, и если бы это было так, вы бы здесь не читали, не так ли?

Прежде всего, двойной целочисленный класс DoubleInt.java. Не самый сложный для понимания, и я не беспокоили с истинной инкапсуляцией (личных данных с сеттеров и добытчиками), так как это только вспомогательный класс, и не нуждается в такой роскоши :-)

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

Далее фактический код, чтобы сделать объединения и сортировки, 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(); 
    } 
} 

и выход из этого будет (форматированный выглядеть лучше):

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

который отсортирован б y сумма отдельных значений. Изменение нагнетательной линии для a.inject (new int[] {10,3,50,90,2,60,12,24,36,1}); результатов в:

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)   

, где вы можете увидеть поведение дублирующих сумм (13, 60 и 62) - массив Java рода является стабильным, если я правильно помню.

Answer 2

Сначала основные варианты: вы можете сначала сгенерировать перестановки, а затем отсортировать их или создать их таким образом, чтобы они сортировались с самого начала. Если производительность не имеет большого значения, я бы пошел первым, потому что это проще.

Создание перестановок прямолинейно, и вы можете использовать Collections.sort для их сортировки.