Подтвердить что ты не робот

Учитывая машину, которая может сортировать по 5 объектов. Как быстро мы можем сортировать 25 из них?

Предположим, что у вас есть 25 объектов и машина, которая может сортировать по 5 из них по некоторым критериям, которые вы даже не знаете. Стоимость использования этой машины очень дорогая (1 $за один запуск), так какова минимальная стоимость сортировки всех ваших объектов?

Мое текущее решение очень просто (аналогичная идея merge sort):

  • Случайно разделить их на 5 групп из 5 объектов
  • Сортировка каждой из них (+5 запусков)
  • Теперь отсортируйте минимальные элементы этих пяти групп (запуск +1)
  • Теперь мы имеем минимальный элемент всего множества. Удалите его из группы, к которой она принадлежит, и повторите шаг 3 до тех пор, пока в целом не останется только 5 несортированных объектов (запуск +19)
  • Отсортировать остальные 5 объектов (+1 запуск)

Итак, в общем, мы должны заплатить 26 $ (26 запусков).

Вопрос: Есть ли способ сделать его более дешевым (сортировать их по наименьшему количеству запусков)?

4b9b3361

ОТВЕТЫ

Ответ 1

Вот жадный алгоритм выбора объектов для сортировки на каждой итерации:

Сортировка 25 объектов a i совпадает с полностью заполнением таблицы M 25x25, где M i, j= 1, если a i > a j и -1 в противном случае. После того, как вы выполните одну итерацию сортировки с машиной, вы получите непосредственные отношения между отсортированными вами элементами (до 5 ячеек сразу же заполнены), но после этого вы можете заполнить больше ячеек с помощью коммутативности (т.е. Если a > b, то вы знаете, что b < a) и транзитивность (то есть, если a > b и b > c, то вы знаете, что a > c).

Чтобы выбрать 5 элементов для следующей сортировки, вы выбираете элементы, для которых в перекрестках между строками и столбцами, соответствующими этим элементам, есть большинство пустых ячеек. Для этого вы можете просто сравнить все возможные комбинации. Есть 25 вариантов 5 = 53130 возможных вариантов, и сложность на самом деле экспоненциальна, но это не стоит никаких "денег" в этой проблеме.

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

Это не идеально, но довольно эффективно. Я протестировал этот метод на случайных перестановках, а результат в среднем составляет около 16,8 $. Вот пример кода в Python:

import random
import itertools


class SortingMachine:
    def __init__(self):
        self.coins = 0

    def sort(self, elements):
        assert(len(elements) == 5)
        self.coins += 1
        return list(sorted(elements))


def test_sorting(seq):
    N = len(seq)
    machine = SortingMachine()
    table = [[0 if i == j else None for j in range(N)] for i in range(N)]

    # Fill empty table cells using transitivity with Floyd-Warshall algorithm
    def fill_transitive():
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if table[i][j] is None and table[i][k] == table[k][j]:
                        table[i][j] = table[i][k]

    # Register in the table the information that seq[i] > seq[j]
    def set_greater(i, j):
        table[i][j] = 1
        table[j][i] = -1

    # Register in the table information from 5 sorted elements
    def register_sorted(sub):
        for (el1, i1), (el2, i2) in zip(sub, sub[1:]):
            set_greater(i2, i1)

    # Select 5 elements to send to the machine
    def choose_elements():
        # Count empty cells in the cells corresponding to 5 comb elements
        def empty_cells(comb):
            return sum(table[i][j] is None 
                       for i, el1 in comb for j, el2 in comb)
        comb = max((empty_cells(comb), comb) 
                   for comb in itertools.combinations(enumerate(seq), 5))[1]
        return [(el, ind) for ind, el in comb]

    # Return True if the table is completely filled
    def is_complete():
        return all(all(el is not None for el in row) for row in table)

    while not is_complete():
        chosen = choose_elements()
        sorted_chosen = machine.sort(chosen)
        register_sorted(sorted_chosen)
        fill_transitive()

    # Checking that the sorting is correct
    sorted_seq = list(sorted(seq))
    assert(all(sorted_seq.index(seq[ind]) == (sum(row) + N - 1) // 2 
               for ind, row in enumerate(table)))

    return machine.coins


def random_sequence():
    l = list(range(25))
    random.shuffle(l)
    return l

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

Ответ 2

Вы явно не используете эту информацию очень хорошо. Предположим, что A1, B1, C1, D1, E1 являются наименьшими в своих группах, и вы только обнаружили, что D1 был самым маленьким в целом. Затем вы сортируете A1, B1, C1, D2 и E1. Это явно неэффективно, так как вы знаете порядка четырех из них.

Предположим, что они вышли в порядке D1, A1, C1, E1, B1. Вы удалили D1. Какие предметы могут быть самыми маленькими? Только A1 и D2. Какие предметы могут быть вторыми? Только A1, C1, D2, D3 и A2. Итак, вы сортируете эти пять, а два самых маленьких - самые маленькие.

После этого ситуация немного сложна, но мы можем определенно найти самую большую, затем две следующие по величине, затем снова следующую по величине и т.д., поэтому у нас есть пять начальных сортов, еще 14 видов, чтобы найти 21 наименьший, и один окончательный sort = 20 всего. Вероятно, мы можем сделать лучше, но тогда это усложняется.

Ответ 3

Я пробовал другую идею с этой проблемой: что-то вроде Quicksort. Учитывая набор элементов для сортировки таким образом, с потенциальной частичной информацией о порядке между элементами, мы пытаемся найти хороший "поворот" около середины набора, а затем выполнить операции сортировки, которые сравнивают 4 других элемента с точкой поворота в чтобы разделить набор на подмножество меньше, чем точка поворота, и подмножество, большее, чем точка поворота. Затем мы сортируем каждое подмножество аналогичным образом.

Изначально у нас нет информации о заказе, поэтому мы выбираем пять элементов наугад и сортируем их. Тогда средний элемент этих пяти является хорошим выбором для стержня. Затем мы можем продолжить этот поворот или пересмотреть наш выбор, поскольку появляется больше информации.

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

Использование различных различных сводных методов, по-видимому, занимает от 16,85 до 16,95 шагов в среднем и не более 20 шагов (в случайной выборке, которую я взял). Кроме того, этот метод очень быстрый, используя только линейные эвристики времени, чтобы найти шарнир и другие четыре элемента для сортировки на каждом шаге.

Здесь пересмотренная структура графического интерфейса:

package org.jgrapht.demo;

import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Color;
import java.awt.EventQueue;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BoxLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.UIManager;

public class FiveSort extends JFrame {

  private static final long serialVersionUID = 1L;
  private Font smallFont = new Font(Font.DIALOG, Font.PLAIN, 12);
  private Font largeFont = new Font(Font.DIALOG, Font.PLAIN, 36);
  private JLabel stepsLabel = new JLabel("0");
  private JLabel maxLabel = new JLabel("0");
  private JLabel averageLabel = new JLabel("");
  private int rounds = 0;
  private int totalSteps = 0;
  private double averageSteps = 0;
  private int maxSteps = 0;

  public static void main(String[] args) {
    EventQueue.invokeLater(new Runnable() {
      @Override
      public void run() {
        new FiveSort();
      }
    });
  }

  public FiveSort() {
    initGUI();
    setLocationRelativeTo(null);
    setTitle("Five Sort");
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    pack();
    setVisible(true);
  }

  public void initGUI() {
    try {
      // UIManager.setLookAndFeel( UIManager.getCrossPlatformLookAndFeelClassName() );
      UIManager.setLookAndFeel( UIManager.getSystemLookAndFeelClassName() );
    } catch (Exception e) {
      e.printStackTrace();
    }

    // title label
    JLabel titleLabel = new JLabel("Five Sort");
    titleLabel.setFont(largeFont);
    titleLabel.setBackground(Color.BLACK);
    titleLabel.setForeground(Color.WHITE);
    titleLabel.setOpaque(true);
    titleLabel.setHorizontalAlignment(JLabel.CENTER);
    add(titleLabel,BorderLayout.PAGE_START);

    // main panel 
    JPanel mainPanel = new JPanel();
    mainPanel.setLayout(new BoxLayout(mainPanel,BoxLayout.Y_AXIS));
    add(mainPanel);

    // graph panel
    FiveSortPanel graphPanel = new FiveSortPanel();
    mainPanel.add(graphPanel,BorderLayout.CENTER);

    // stats panel
    JPanel statsPanel = new JPanel();
    statsPanel.setBackground(Color.BLACK);
    mainPanel.add(statsPanel);

    JLabel stepsTitleLabel = new JLabel("Current Steps: ");
    stepsTitleLabel.setFont(smallFont);
    stepsTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(stepsTitleLabel);
    stepsLabel.setFont(largeFont);
    stepsLabel.setForeground(Color.WHITE);
    stepsLabel.setText("" + graphPanel.getSteps());
    statsPanel.add(stepsLabel);

    JLabel maxTitleLabel = new JLabel("Max Steps: ");
    maxTitleLabel.setFont(smallFont);
    maxTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(maxTitleLabel);
    maxLabel.setFont(largeFont);
    maxLabel.setForeground(Color.WHITE);
    maxLabel.setText("" + maxSteps);
    statsPanel.add(maxLabel);

    JLabel averageTitleLabel = new JLabel("Avg Steps: ");
    averageTitleLabel.setFont(smallFont);
    averageTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(averageTitleLabel);
    averageLabel.setFont(largeFont);
    averageLabel.setForeground(Color.WHITE);
    averageLabel.setText("");
    statsPanel.add(averageLabel);

    // button panel
    JPanel buttonPanel = new JPanel();
    buttonPanel.setBackground(Color.BLACK);
    add(buttonPanel,BorderLayout.PAGE_END);

    Button newButton = new Button("Step");
    newButton.setFocusable(false);
    newButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (!graphPanel.isComplete()) {
          graphPanel.step();
          stepsLabel.setText("" + graphPanel.getSteps());
        }
      }
    });
    buttonPanel.add(newButton);

    Button restartButton = new Button("Restart");
    restartButton.setFocusable(false);
    restartButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (graphPanel.isComplete()) {
          ++rounds;
          totalSteps += graphPanel.getSteps();
          averageSteps = ((int)(totalSteps / (double)rounds * 10))/10.0; 
          maxSteps = Math.max(maxSteps, graphPanel.getSteps());
        }
        graphPanel.restart();
        stepsLabel.setText("" + graphPanel.getSteps());
        maxLabel.setText("" + maxSteps);
        averageLabel.setText("" + averageSteps);
      }
    });
    buttonPanel.add(restartButton);

    Button run50Button = new Button("Run 50");
    run50Button.setFocusable(false);
    run50Button.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        int currentRounds = 0;
        while (currentRounds < 50) {
          if (!graphPanel.isComplete()) {
            graphPanel.step();
            stepsLabel.setText("" + graphPanel.getSteps());
          } else {
            ++rounds;
            ++currentRounds;
            totalSteps += graphPanel.getSteps();
            averageSteps = ((int)(totalSteps / (double)rounds * 100))/100.0; 
            maxSteps = Math.max(maxSteps, graphPanel.getSteps());
            graphPanel.restart();
            stepsLabel.setText("" + graphPanel.getSteps());
            maxLabel.setText("" + maxSteps);
            averageLabel.setText("" + averageSteps);
          }
        }
      }
    });
    buttonPanel.add(run50Button);
  }

}

И здесь пересмотренные подпрограммы обработки графики (которые требуют jgrapht-ext-0.9.1-uber.jar, свободно доступных с сайта JGraphT):

package org.jgrapht.demo;

import java.awt.Dimension;
import java.awt.GridBagLayout;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import javax.swing.JPanel;
import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.ListenableGraph;
import org.jgrapht.alg.StrongConnectivityInspector;
import org.jgrapht.alg.TransitiveClosure;
import org.jgrapht.ext.JGraphXAdapter;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.ListenableDirectedGraph;
import org.jgrapht.graph.SimpleDirectedGraph;

import com.mxgraph.layout.mxCircleLayout;
import com.mxgraph.swing.mxGraphComponent;
import com.mxgraph.util.mxConstants;

public class FiveSortPanel extends JPanel {
  private static final long serialVersionUID = 1L;
  private static final int ARRAY_SIZE = 25;
  private static final int SORT_SIZE = 5;
  private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  private static final String STROKE_YELLOW = "strokeColor=#CCCC00";
  private Integer[][] BIBD = { 
    {1,2,3,4,5},     {6,7,8,9,10},    {11,12,13,14,15}, {16,17,18,19,20}, {21,22,23,24,0},
    {1,6,11,16,21},  {2,7,12,17,21},  {3,8,13,18,21},   {4,9,14,19,21},   {5,10,15,20,21},
    {2,8,14,20,22},  {3,10,11,19,22}, {5,9,12,16,22},   {1,7,15,18,22},   {4,6,13,17,22},
    {3,9,15,17,23},  {5,6,14,18,23},  {4,7,11,20,23},   {2,10,13,16,23},  {1,8,12,19,23},
    {4,10,12,18,24}, {1,9,13,20,24},  {2,6,15,19,24},   {5,8,11,17,24},   {3,7,14,16,24},
    {5,7,13,19,0},   {4,8,15,16,0},   {1,10,14,17,0},   {3,6,12,20,0},    {2,9,11,18,0}
  }; 
  private int steps = 0;
  private boolean complete = false;
  class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
    String label;
    T value;
    Node(String label, T value) {
      this.label = label;
      this.value = value;
    }
    @Override
    public String toString() {
      return label + ": " + value.toString();
    }
    @Override
    public int compareTo(Node<T> other) {
      return value.compareTo(other.value);
    }
  }
  // g represents all potential orders; starts as complete graph
  private ListenableGraph<Node<Integer>, DefaultEdge> g;
  // g1 represents all actual orders; starts with no edges
  private SimpleDirectedGraph<Node<Integer>, DefaultEdge> g1;
  private JGraphXAdapter<Node<Integer>, DefaultEdge> jgxAdapter;
  @SuppressWarnings("unchecked")
  Node<Integer>[] vertexArray = new Node[ARRAY_SIZE];
  List<Set<Node<Integer>>> connectedComponentsOfG;
  HashMap<Node<Integer>,com.mxgraph.model.mxICell> vertexToCellMap;
  HashMap<DefaultEdge,com.mxgraph.model.mxICell> edgeToCellMap;
  // sort sets in descending order by number of elements
  public class SetComparator implements Comparator<Set<Node<Integer>>> {
    @Override
    public int compare(Set<Node<Integer>> s1, Set<Node<Integer>> s2) {
      return s2.size() - s1.size();
    }
  }
  TransitiveClosure transitiveClosure = TransitiveClosure.INSTANCE;
  public enum SortType { RANDOM_BIBD, PIVOT_LINEAR, PIVOT_QUADRATIC, PIVOT_RATIO };
  SortType sortType = SortType.PIVOT_RATIO;

  public FiveSortPanel() {
    Dimension size = new Dimension(600,600);
    setPreferredSize(size);
    setLayout(new GridBagLayout());
    restart();
  }

  public int getSteps() {
    return steps;
  }

  public boolean isComplete() {
    return complete;
  }

  private void updateConnectedComponents() {
    @SuppressWarnings("unchecked")
    StrongConnectivityInspector<Node<Integer>,DefaultEdge> sci 
      = new StrongConnectivityInspector<Node<Integer>,DefaultEdge>(
          (DirectedGraph<Node<Integer>, DefaultEdge>) g);
    connectedComponentsOfG = sci.stronglyConnectedSets();
    Collections.sort(connectedComponentsOfG, new SetComparator());
  }

  public void step() {
    if (!complete) {
      chooseFiveAndSort();
      ++steps;
    }
    updateConnectedComponents();
    complete = true;
    for (Set<Node<Integer>> s : connectedComponentsOfG) {
      if (s.size() > 1) {
        complete = false;
      }
    }
  }

  public void restart() {
    removeAll();
    steps = 0;
    complete = false;
    if (sortType == SortType.RANDOM_BIBD) {
      shuffleBIBD();
    }
    g = new ListenableDirectedGraph<Node<Integer>, DefaultEdge>(DefaultEdge.class);
    g1 = new SimpleDirectedGraph<Node<Integer>, DefaultEdge>(DefaultEdge.class);
    jgxAdapter = new JGraphXAdapter<Node<Integer>, DefaultEdge>(g);
    vertexToCellMap = jgxAdapter.getVertexToCellMap();
    edgeToCellMap = jgxAdapter.getEdgeToCellMap();
    jgxAdapter.getStylesheet().getDefaultEdgeStyle().put(mxConstants.STYLE_NOLABEL, "1");
    add(new mxGraphComponent(jgxAdapter));
    ArrayList<Integer> permutation = new ArrayList<Integer>();
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      permutation.add(i);
    }
    Collections.shuffle(permutation);
    @SuppressWarnings("unchecked")
    Node<Integer>[] n = new Node[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      n[i] = new Node<Integer>(ALPHABET.substring(i, i+1), permutation.get(i));
      vertexArray[i] = n[i];
      g.addVertex(n[i]);
      g1.addVertex(n[i]);
      for (int j = 0; j < i; ++j) {
        g.addEdge(n[i], n[j]);
        g.addEdge(n[j], n[i]);
      }
    }
    updateConnectedComponents();
    mxCircleLayout layout = new mxCircleLayout(jgxAdapter);
    layout.execute(jgxAdapter.getDefaultParent());
    validate();
    repaint();
  }

  private void chooseFiveAndSort() {
    Node<Integer>[] fiveNodes = chooseFive();
    for (int i = 0; i < fiveNodes.length-1; ++i) {
      g1.addEdge(fiveNodes[i],fiveNodes[i+1]);
    }
    transitiveClosure.closeSimpleDirectedGraph(g1);
    List<Object> edgeCellList = new ArrayList<Object>();
    for (int i = 0; i < fiveNodes.length-1; ++i) {
      List<Node<Integer>> predList = Graphs.predecessorListOf(g1,fiveNodes[i]);
      predList.add(fiveNodes[i]);
      List<Node<Integer>> succList = Graphs.successorListOf(g1,fiveNodes[i+1]);
      succList.add(fiveNodes[i+1]);
      for (Node<Integer> np : predList) {
        for (Node<Integer> ns : succList) {
          g.removeEdge(ns,np);
          edgeCellList.add((Object)(edgeToCellMap.get(g.getEdge(np, ns))));
        }
      }
    }
    if (edgeCellList != null) {
      jgxAdapter.setCellStyle(STROKE_YELLOW, edgeCellList.toArray());
    }
  }

  private void shuffleBIBD() {
    List<Integer[]> BIBDList = (List<Integer[]>) Arrays.asList(BIBD);
    Collections.shuffle(BIBDList);
    BIBD = BIBDList.toArray(new Integer[0][0]);
  }

  private Node<Integer>[] chooseFiveRandomBIBD() {
    @SuppressWarnings("unchecked")
    Node<Integer>[] nodeArray = new Node[SORT_SIZE];
    Integer[] indexArray = BIBD[steps];
    for (int i = 0; i < SORT_SIZE; ++i) {
      nodeArray[i] = vertexArray[indexArray[i]];
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  }

  private Node<Integer>[] chooseFive() {
    switch (sortType) {
    case RANDOM_BIBD:
      return chooseFiveRandomBIBD();
    case PIVOT_LINEAR:
      return chooseFivePivotLinear();
    case PIVOT_QUADRATIC:
      return chooseFivePivotQuadratic();
    case PIVOT_RATIO:
      return chooseFivePivotRatio();
    default:
      System.err.println("Internal error: unknown sorting method");
      System.exit(1);
    }
    return null; // inaccessible   
  }

  private Node<Integer>[] chooseFivePivotLinear() {
    @SuppressWarnings("unchecked")
    Node<Integer>[] nodeArray = new Node[SORT_SIZE];
    @SuppressWarnings("unchecked")
    Set<Node<Integer>> largestSCC = 
      (Set<Node<Integer>>) (((HashSet<Node<Integer>>) connectedComponentsOfG.get(0)).clone());
    int s = largestSCC.size();
    if (s >= 5) {
      Node<Integer> pivot = largestSCC.iterator().next();
      int pivotDegree = g1.inDegreeOf(pivot) + g1.outDegreeOf(pivot);
      int pivotSymmetry = g1.inDegreeOf(pivot) - g1.outDegreeOf(pivot);
      for (Node<Integer> n : largestSCC) {
        int nDegree = g1.inDegreeOf(n) + g1.outDegreeOf(n);
        int nSymmetry = g1.inDegreeOf(n) - g1.outDegreeOf(n);
        if (nDegree >= pivotDegree) {
          if (Math.abs(nSymmetry) < Math.abs(pivotSymmetry)) {
            pivot = n;
            pivotDegree = nDegree;
            pivotSymmetry = nSymmetry;
          }
        }
      }
      int chosen = 0;
      nodeArray[chosen++] = pivot;
      largestSCC.remove(pivot);
      int desiredConnections = 0;
      while (chosen < SORT_SIZE) {
        Iterator<Node<Integer>> iter = largestSCC.iterator();
        while (iter.hasNext()) {
          Node<Integer> n = iter.next();
          int connectionsWithN = 0;
          for (Node<Integer> n1 : nodeArray) {
            if (g1.containsEdge(n,n1)) ++connectionsWithN;
            if (g1.containsEdge(n1,n)) ++connectionsWithN;
          }
          if (connectionsWithN <= desiredConnections) {
            nodeArray[chosen++] = n;
            iter.remove();
            if (chosen == SORT_SIZE) break;
          }
        }
        ++desiredConnections;
      }
    } else if (s == 4) { // take all 4 elements and 1 from elsewhere (which doesn't help)
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
    } else if (s == 3) { // take all 3 elements and find 2 from elsewhere
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Set<Node<Integer>> scc : connectedComponentsOfG) { // prefer size 2 component
        if (scc.size() == 2) {
          for (Node<Integer> n : scc) {
            nodeArray[chosen++] = n;
          }
          break;
        }
      }
      if (chosen < SORT_SIZE) { // no size 2 component found 
        if (connectedComponentsOfG.get(1).size() == 3) { // take 2
          Iterator<Node<Integer>> iter = connectedComponentsOfG.get(1).iterator();
          nodeArray[chosen++] = iter.next();
          nodeArray[chosen++] = iter.next();
        } else {
          nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
          nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
        }
      }
    } else if (s == 2) { // take both; all from next SCC, and 1 from next, and 1 more if nec. 
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Node<Integer> n : connectedComponentsOfG.get(1)) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
      if (connectedComponentsOfG.get(1).size() == 1) {
        nodeArray[chosen++] = connectedComponentsOfG.get(3).iterator().next();
      }
    } else if (s == 1) {
      System.err.println("Internal Error: should have been complete by now");
      System.exit(1);
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  } 

  private Node<Integer>[] chooseFivePivotQuadratic() {
    @SuppressWarnings("unchecked")
    Node<Integer>[] nodeArray = new Node[SORT_SIZE];
    @SuppressWarnings("unchecked")
    Set<Node<Integer>> largestSCC = 
      (Set<Node<Integer>>) (((HashSet<Node<Integer>>) connectedComponentsOfG.get(0)).clone());
    int s = largestSCC.size();
    if (s >= 5) {
      Node<Integer> pivot = largestSCC.iterator().next();
      double pivotDegree = 7*g1.inDegreeOf(pivot) * g1.outDegreeOf(pivot) 
          - (g1.inDegreeOf(pivot)) * (g1.inDegreeOf(pivot))
          - (g1.outDegreeOf(pivot)) - (g1.outDegreeOf(pivot));
      for (Node<Integer> n : largestSCC) {
        double nDegree = 7*g1.inDegreeOf(n) * g1.outDegreeOf(n) 
            - (g1.inDegreeOf(n)) * (g1.inDegreeOf(n))
            - (g1.outDegreeOf(n)) - (g1.outDegreeOf(n));
        if (nDegree >= pivotDegree) {
          pivot = n;
          pivotDegree = nDegree;
        }
      }
      int chosen = 0;
      nodeArray[chosen++] = pivot;
      largestSCC.remove(pivot);
      int desiredConnections = 0;
      while (chosen < SORT_SIZE) {
        Iterator<Node<Integer>> iter = largestSCC.iterator();
        while (iter.hasNext()) {
          Node<Integer> n = iter.next();
          int connectionsWithN = 0;
          for (Node<Integer> n1 : nodeArray) {
            if (g1.containsEdge(n,n1)) ++connectionsWithN;
            if (g1.containsEdge(n1,n)) ++connectionsWithN;
          }
          if (connectionsWithN <= desiredConnections) {
            nodeArray[chosen++] = n;
            iter.remove();
            if (chosen == SORT_SIZE) break;
          }
        }
        ++desiredConnections;
      }
    } else if (s == 4) { // take all 4 elements and 1 from elsewhere (which doesn't help)
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
    } else if (s == 3) { // take all 3 elements and find 2 from elsewhere
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Set<Node<Integer>> scc : connectedComponentsOfG) { // prefer size 2 component
        if (scc.size() == 2) {
          for (Node<Integer> n : scc) {
            nodeArray[chosen++] = n;
          }
          break;
        }
      }
      if (chosen < SORT_SIZE) { // no size 2 component found 
        if (connectedComponentsOfG.get(1).size() == 3) { // take 2
          Iterator<Node<Integer>> iter = connectedComponentsOfG.get(1).iterator();
          nodeArray[chosen++] = iter.next();
          nodeArray[chosen++] = iter.next();
        } else {
          nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
          nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
        }
      }
    } else if (s == 2) { // take both; all from next SCC, and 1 from next, and 1 more if nec. 
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Node<Integer> n : connectedComponentsOfG.get(1)) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
      if (connectedComponentsOfG.get(1).size() == 1) {
        nodeArray[chosen++] = connectedComponentsOfG.get(3).iterator().next();
      }
    } else if (s == 1) {
      System.err.println("Internal Error: should have been complete by now");
      System.exit(1);
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  }

  private Node<Integer>[] chooseFivePivotRatio() {
    @SuppressWarnings("unchecked")
    Node<Integer>[] nodeArray = new Node[SORT_SIZE];
    @SuppressWarnings("unchecked")
    Set<Node<Integer>> largestSCC = 
      (Set<Node<Integer>>) (((HashSet<Node<Integer>>) connectedComponentsOfG.get(0)).clone());
    int s = largestSCC.size();
    if (s >= 5) {
      Node<Integer> pivot = largestSCC.iterator().next();
      int pivotMinInOut = Math.min(g1.inDegreeOf(pivot),g1.outDegreeOf(pivot));
      int pivotMaxInOut = Math.max(g1.inDegreeOf(pivot),g1.outDegreeOf(pivot)); 
      double pivotRatio = (pivotMaxInOut == 0) ? 0 : pivotMinInOut/((double)pivotMaxInOut);
      for (Node<Integer> n : largestSCC) {
        int nMinInOut = Math.min(g1.inDegreeOf(n),g1.outDegreeOf(n));
        int nMaxInOut = Math.max(g1.inDegreeOf(n),g1.outDegreeOf(n)); 
        double nRatio = (nMaxInOut == 0) ? 0 : nMinInOut/((double)nMaxInOut);
        if (nRatio > pivotRatio) {
          pivot = n;
          pivotRatio = nRatio;
        }
      }
      int chosen = 0;
      nodeArray[chosen++] = pivot;
      largestSCC.remove(pivot);
      int desiredConnections = 0;
      while (chosen < SORT_SIZE) {
        Iterator<Node<Integer>> iter = largestSCC.iterator();
        while (iter.hasNext()) {
          Node<Integer> n = iter.next();
          int connectionsWithN = 0;
          for (Node<Integer> n1 : nodeArray) {
            if (g1.containsEdge(n,n1)) ++connectionsWithN;
            if (g1.containsEdge(n1,n)) ++connectionsWithN;
          }
          if (connectionsWithN <= desiredConnections) {
            nodeArray[chosen++] = n;
            iter.remove();
            if (chosen == SORT_SIZE) break;
          }
        }
        ++desiredConnections;
      }
    } else if (s == 4) { // take all 4 elements and 1 from elsewhere (which doesn't help)
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
    } else if (s == 3) { // take all 3 elements and find 2 from elsewhere
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Set<Node<Integer>> scc : connectedComponentsOfG) { // prefer size 2 component
        if (scc.size() == 2) {
          for (Node<Integer> n : scc) {
            nodeArray[chosen++] = n;
          }
          break;
        }
      }
      if (chosen < SORT_SIZE) { // no size 2 component found 
        if (connectedComponentsOfG.get(1).size() == 3) { // take 2
          Iterator<Node<Integer>> iter = connectedComponentsOfG.get(1).iterator();
          nodeArray[chosen++] = iter.next();
          nodeArray[chosen++] = iter.next();
        } else {
          nodeArray[chosen++] = connectedComponentsOfG.get(1).iterator().next();
          nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
        }
      }
    } else if (s == 2) { // take both; all from next SCC, and 1 from next, and 1 more if nec. 
      int chosen = 0;
      for (Node<Integer> n : largestSCC) {
        nodeArray[chosen++] = n;
      }
      for (Node<Integer> n : connectedComponentsOfG.get(1)) {
        nodeArray[chosen++] = n;
      }
      nodeArray[chosen++] = connectedComponentsOfG.get(2).iterator().next();
      if (connectedComponentsOfG.get(1).size() == 1) {
        nodeArray[chosen++] = connectedComponentsOfG.get(3).iterator().next();
      }
    } else if (s == 1) {
      System.err.println("Internal Error: should have been complete by now");
      System.exit(1);
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  }

}

Ответ 4

Один интересный угол в этом вопросе - идея использования "комбинаторных блочных конструкций". Мы хотим, чтобы каждый из наших видов предоставлял нам как можно больше информации, поэтому мы не хотим, чтобы одна и та же пара элементов находилась в двух разных типах. Это реально достижимо: мы можем использовать комбинаторную структуру, называемую "сбалансированным неполным блочным дизайном" (BIBD). Мы ищем (25,5,1) -BIBD, что означает 25 элементов (25), заблокированных по пять за раз (5), так что каждая пара элементов отображается ровно в один блок (1).

Такие конструкции блоков были широко изучены. Оказывается, что существует (25,5,1) -BIBD. Явная конструкция приведена, например, http://arxiv.org/ftp/arxiv/papers/0909/0909.3533.pdf страница 8.

{(1,2,3,4,5) (6,7,8,9,10) (11,12,13,14,15) (16,17,18,19,20) (21,22,23,24,25)
(1,6,11,16,21) (2,7,12,17,21) (3,8,13,18,21) (4,9,14,19,21) (5,10,15,20,21)
(2,8,14,20,22) (3,10,11,19,22) (5,9,12,16,22) (1,7,15,18,22) (4,6,13,17,22)
(3,9,15,17,23) (5,6,14,18,23) (4,7,11,20,23) (2,10,13,16,23) (1,8,12,19,23)
(4,10,12,18,24) (1,9,13,20,24) (2,6,15,19,24) (5,8,11,17,24) (3,7,14,16,24)
(5,7,13,19,25) (4,8,15,16,25) (1,10,14,17,25) (3,6,12,20,25) (2,9,11,18,25)}

Sage также можно использовать для построения BIBD.

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

Обновление

Оказалось, что мое предложение не очень полезно использовать в этой задаче, за исключением того, чтобы поместить верхнюю границу числа шагов в решении (30, размер BIBD). Чтобы оценить его производительность, я написал некоторое "тестовое постельное" программное обеспечение (см. Ниже), которое дает визуальное представление о ходе сортировки.

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

g начинается с 600 ребер, каждый из 25 * 24 направленных ребер между двумя элементами. Мы выполняем, когда g не имеет нетривиальных (то есть размер более 1) сильно связанных компонентов, и в этом случае g может быть однозначно перенаправлено на то, чтобы дать правильный порядок. Это происходит, когда в g имеется ровно 300 ребер. Аналогично, g1 начинается без краев, и мы делаем это, когда в g1 появляются такие же 300 ребер, что и в g.

Выбор 5 элементов, а затем их сортировка сразу добавляет до 5 + 4 + 3 + 2 + 1 = 15 новых ребер в g (и удаляет одинаковое количество ребер из g1). Я говорю "до", потому что, если какой-либо из этих ребер уже находится в g, они не добавляются к счету. Итак, если мы уже знаем A → B и ничего не знаем об отношениях между любой другой парой в A, B, C, D, E, то сортировка этих пяти дает только 14 новых ребер в g.

С другой стороны, мы часто можем получить больше стрелок из рода, используя транзитивность. Если мы знаем, что B → F, а вид говорит нам, что A → B, мы можем сделать вывод, что A → F, что является дополнительной стрелкой в ​​g. Множество всех дополнительных стрелок, найденных через транзитивность, можно получить, найдя "транзитивное замыкание" g с новыми стрелками, добавленными в результате сортировки. Соответствующий эффект на g1 можно легко найти.

В моем программном обеспечении ниже я даю изображение графа g1, который начинается с 600 направленных краев, изображенных как 300 синих краев со стрелками на каждом конце. Каждый шаг сортировки, за которым следует транзитное закрытие, заменит несколько двукратных синих стрелок односторонними желтыми стрелками. Мы знаем, что мы закончили, когда все синие стрелы исчезли; эквивалентно, когда g1 не имеет нетривиальных сильно связанных компонент.

В приведенном ниже программном обеспечении я выбрал 5 элементов для сортировки, выбрав случайный неиспользуемый блок из BIBD, который я дал ранее, а затем пометил блок как используемый. Как правило, все 30 блоков сортируют по 25 предметам таким образом. Как видно из визуализации, процесс начинается достаточно хорошо, но пропускает очевидные ускорения с шагов с 20 по 30. Я пришел к выводу, что самые быстрые решения этой проблемы должны быть адаптивными, выбор 5 предметов для сортировки на основе предыдущих результатов.

Рассмотрение проблемы таким образом дало мне несколько новых идей, которые я могу исследовать в другом ответе на вопрос. Между тем, вот два класса Java для используемой мной программы.

Рамка GUI:

package org.jgrapht.demo;

import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Color;
import java.awt.EventQueue;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BoxLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.UIManager;

public class FiveSort extends JFrame {

  private static final long serialVersionUID = 1L;
  private Font smallFont = new Font(Font.DIALOG, Font.PLAIN, 12);
  private Font largeFont = new Font(Font.DIALOG, Font.PLAIN, 36);
  private JLabel stepsLabel = new JLabel("0");
  private JLabel maxLabel = new JLabel("0");
  private JLabel averageLabel = new JLabel("");
  private int rounds = 0;
  private int totalSteps = 0;
  private double averageSteps = 0;
  private int maxSteps = 0;

  public static void main(String[] args) {
    EventQueue.invokeLater(new Runnable() {
      @Override
      public void run() {
        new FiveSort();
      }
    });
  }

  public FiveSort() {
    initGUI();
    setLocationRelativeTo(null);
    setTitle("Five Sort");
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    pack();
    setVisible(true);
  }

  public void initGUI() {
    try {
      // UIManager.setLookAndFeel( UIManager.getCrossPlatformLookAndFeelClassName() );
      UIManager.setLookAndFeel( UIManager.getSystemLookAndFeelClassName() );
    } catch (Exception e) {
      e.printStackTrace();
    }

    // title label
    JLabel titleLabel = new JLabel("Five Sort");
    titleLabel.setFont(largeFont);
    titleLabel.setBackground(Color.BLACK);
    titleLabel.setForeground(Color.WHITE);
    titleLabel.setOpaque(true);
    titleLabel.setHorizontalAlignment(JLabel.CENTER);
    add(titleLabel,BorderLayout.PAGE_START);

    // main panel 
    JPanel mainPanel = new JPanel();
    mainPanel.setLayout(new BoxLayout(mainPanel,BoxLayout.Y_AXIS));
    add(mainPanel);

    // graph panel
    FiveSortPanel graphPanel = new FiveSortPanel();
    mainPanel.add(graphPanel,BorderLayout.CENTER);

    // stats panel
    JPanel statsPanel = new JPanel();
    statsPanel.setBackground(Color.BLACK);
    mainPanel.add(statsPanel);

    JLabel stepsTitleLabel = new JLabel("Current Steps: ");
    stepsTitleLabel.setFont(smallFont);
    stepsTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(stepsTitleLabel);
    stepsLabel.setFont(largeFont);
    stepsLabel.setForeground(Color.WHITE);
    stepsLabel.setText("" + graphPanel.getSteps());
    statsPanel.add(stepsLabel);

    JLabel maxTitleLabel = new JLabel("Max Steps: ");
    maxTitleLabel.setFont(smallFont);
    maxTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(maxTitleLabel);
    maxLabel.setFont(largeFont);
    maxLabel.setForeground(Color.WHITE);
    maxLabel.setText("" + maxSteps);
    statsPanel.add(maxLabel);

    JLabel averageTitleLabel = new JLabel("Avg Steps: ");
    averageTitleLabel.setFont(smallFont);
    averageTitleLabel.setForeground(Color.WHITE);
    statsPanel.add(averageTitleLabel);
    averageLabel.setFont(largeFont);
    averageLabel.setForeground(Color.WHITE);
    averageLabel.setText("");
    statsPanel.add(averageLabel);

    // button panel
    JPanel buttonPanel = new JPanel();
    buttonPanel.setBackground(Color.BLACK);
    add(buttonPanel,BorderLayout.PAGE_END);

    Button newButton = new Button("Step");
    newButton.setFocusable(false);
    newButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (!graphPanel.isComplete()) {
          graphPanel.step();
          stepsLabel.setText("" + graphPanel.getSteps());
        }
      }
    });
    buttonPanel.add(newButton);

    Button restartButton = new Button("Restart");
    restartButton.setFocusable(false);
    restartButton.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        if (graphPanel.isComplete()) {
          ++rounds;
          totalSteps += graphPanel.getSteps();
          averageSteps = ((int)(totalSteps / (double)rounds * 10))/10.0; 
          maxSteps = Math.max(maxSteps, graphPanel.getSteps());
        }
        graphPanel.restart();
        stepsLabel.setText("" + graphPanel.getSteps());
        maxLabel.setText("" + maxSteps);
        averageLabel.setText("" + averageSteps);
      }
    });
    buttonPanel.add(restartButton);
  }

}

Подпрограммы обработки графиков (которые требуют jgrapht-ext-0.9.1-uber.jar, свободно доступных с сайта JGraphT):

package org.jgrapht.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Comparator;
import java.util.List;
import java.util.Set;

import javax.swing.JPanel;

import org.jgrapht.DirectedGraph;
import org.jgrapht.Graphs;
import org.jgrapht.ListenableGraph;
import org.jgrapht.alg.StrongConnectivityInspector;
import org.jgrapht.alg.TransitiveClosure;
import org.jgrapht.ext.JGraphXAdapter;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.ListenableDirectedGraph;
import org.jgrapht.graph.SimpleDirectedGraph;

import com.mxgraph.layout.mxCircleLayout;
import com.mxgraph.swing.mxGraphComponent;
import com.mxgraph.util.mxConstants;

public class FiveSortPanel extends JPanel {
  private static final long serialVersionUID = 1L;
  private static final int ARRAY_SIZE = 25;
  private static final int SORT_SIZE = 5;
  private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  private static final String STROKE_YELLOW = "strokeColor=#CCCC00";
  private Integer[][] BIBD = { 
    {1,2,3,4,5},     {6,7,8,9,10},    {11,12,13,14,15}, {16,17,18,19,20}, {21,22,23,24,0},
    {1,6,11,16,21},  {2,7,12,17,21},  {3,8,13,18,21},   {4,9,14,19,21},   {5,10,15,20,21},
    {2,8,14,20,22},  {3,10,11,19,22}, {5,9,12,16,22},   {1,7,15,18,22},   {4,6,13,17,22},
    {3,9,15,17,23},  {5,6,14,18,23},  {4,7,11,20,23},   {2,10,13,16,23},  {1,8,12,19,23},
    {4,10,12,18,24}, {1,9,13,20,24},  {2,6,15,19,24},   {5,8,11,17,24},   {3,7,14,16,24},
    {5,7,13,19,0},   {4,8,15,16,0},   {1,10,14,17,0},   {3,6,12,20,0},    {2,9,11,18,0}
  }; 
  private int steps = 0;
  private boolean complete = false;
  class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
    String label;
    T value;
    Node(String label, T value) {
      this.label = label;
      this.value = value;
    }
    @Override
    public String toString() {
      return label + ": " + value.toString();
    }
    @Override
    public int compareTo(Node<T> other) {
      return value.compareTo(other.value);
    }
  }
  // g represents all potential orders; starts as complete graph
  private ListenableGraph<Node<Integer>, DefaultEdge> g;
  // g1 represents all actual orders; starts with no edges
  private SimpleDirectedGraph<Node<Integer>, DefaultEdge> g1;
  private JGraphXAdapter<Node<Integer>, DefaultEdge> jgxAdapter;
  @SuppressWarnings("unchecked")
  Node<Integer>[] vertexArray = new Node[ARRAY_SIZE];
  List<Set<Node<Integer>>> connectedComponentsOfG;
  HashMap<Node<Integer>,com.mxgraph.model.mxICell> vertexToCellMap;
  HashMap<DefaultEdge,com.mxgraph.model.mxICell> edgeToCellMap;
  // sort sets in descending order by number of elements
  public class SetComparator implements Comparator<Set<Node<Integer>>> {
    @Override
    public int compare(Set<Node<Integer>> s1, Set<Node<Integer>> s2) {
      return s2.size() - s1.size();
    }
  }
  TransitiveClosure transitiveClosure = TransitiveClosure.INSTANCE;

  public FiveSortPanel() {
    restart();
  }

  public int getSteps() {
    return steps;
  }

  public boolean isComplete() {
    return complete;
  }

  private void updateConnectedComponents() {
    @SuppressWarnings("unchecked")
    StrongConnectivityInspector<Node<Integer>,DefaultEdge> sci 
      = new StrongConnectivityInspector<Node<Integer>,DefaultEdge>(
          (DirectedGraph<Node<Integer>, DefaultEdge>) g);
    connectedComponentsOfG = sci.stronglyConnectedSets();
    Collections.sort(connectedComponentsOfG, new SetComparator());
  }

  public void step() {
    if (!complete) {
      chooseFiveAndSort();
      ++steps;
    }
    updateConnectedComponents();
    complete = true;
    for (Set<Node<Integer>> s : connectedComponentsOfG) {
      if (s.size() > 1) {
        complete = false;
      }
    }
  }

  public void restart() {
    removeAll();
    steps = 0;
    complete = false;
    shuffleBIBD();
    g = new ListenableDirectedGraph<Node<Integer>, DefaultEdge>(DefaultEdge.class);
    g1 = new SimpleDirectedGraph<Node<Integer>, DefaultEdge>(DefaultEdge.class);
    jgxAdapter = new JGraphXAdapter<Node<Integer>, DefaultEdge>(g);
    vertexToCellMap = jgxAdapter.getVertexToCellMap();
    edgeToCellMap = jgxAdapter.getEdgeToCellMap();
    jgxAdapter.getStylesheet().getDefaultEdgeStyle().put(mxConstants.STYLE_NOLABEL, "1");
    add(new mxGraphComponent(jgxAdapter));
    ArrayList<Integer> permutation = new ArrayList<Integer>();
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      permutation.add(i);
    }
    Collections.shuffle(permutation);
    @SuppressWarnings("unchecked")
    Node<Integer>[] n = new Node[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      n[i] = new Node<Integer>(ALPHABET.substring(i, i+1), permutation.get(i));
      vertexArray[i] = n[i];
      g.addVertex(n[i]);
      g1.addVertex(n[i]);
      for (int j = 0; j < i; ++j) {
        g.addEdge(n[i], n[j]);
        g.addEdge(n[j], n[i]);
      }
    }
    updateConnectedComponents();
    mxCircleLayout layout = new mxCircleLayout(jgxAdapter);
    layout.execute(jgxAdapter.getDefaultParent());
    //repaint();
  }

  private void chooseFiveAndSort() {
    Node<Integer>[] fiveNodes = chooseFive();
    for (int i = 0; i < fiveNodes.length-1; ++i) {
      g1.addEdge(fiveNodes[i],fiveNodes[i+1]);
    }
    transitiveClosure.closeSimpleDirectedGraph(g1);
    List<Object> edgeCellList = new ArrayList<Object>();
    for (int i = 0; i < fiveNodes.length-1; ++i) {
      List<Node<Integer>> predList = Graphs.predecessorListOf(g1,fiveNodes[i]);
      predList.add(fiveNodes[i]);
      List<Node<Integer>> succList = Graphs.successorListOf(g1,fiveNodes[i+1]);
      succList.add(fiveNodes[i+1]);
      for (Node<Integer> np : predList) {
        for (Node<Integer> ns : succList) {
          g.removeEdge(ns,np);
          edgeCellList.add((Object)(edgeToCellMap.get(g.getEdge(np, ns))));
        }
      }
    }
    jgxAdapter.setCellStyle(STROKE_YELLOW, edgeCellList.toArray());
  }

  private Node<Integer>[] chooseFive() {
    return chooseFiveRandomBIBD();
  }

  private void shuffleBIBD() {
    List<Integer[]> BIBDList = (List<Integer[]>) Arrays.asList(BIBD);
    Collections.shuffle(BIBDList);
    BIBD = BIBDList.toArray(new Integer[0][0]);
  }

  private Node<Integer>[] chooseFiveRandomBIBD() {
    Integer[] indexArray = BIBD[steps];
    @SuppressWarnings("unchecked")
    Node<Integer>[] nodeArray = new Node[SORT_SIZE];
    for (int i = 0; i < SORT_SIZE; ++i) {
      nodeArray[i] = vertexArray[indexArray[i]];
    }
    Arrays.sort(nodeArray);
    return nodeArray;
  }

}

Ответ 5

Разделим все элементы из 5 групп на 5 элементов, удалим последние 2 элемента из каждой группы (эти числа меньше трех чисел и, конечно, не будут кандидатами на решение). Мы выполняем ту же процедуру несколько раз, пока не придем с одной группой с 5 элементами, которые сортируются в последний раз и берут первые три элемента в качестве решения.

Вот счет операции сортировки

5 groups by 5 elements - 5 sort
25 - 10 = 15 elements in 3 groups - 3 sort
15 - 6 = 9 elements in 2 groups ( one with 4 elements, the other with 5 elements) - 1 sort
4 + 3 = 7 elements in 2 groups ( one with 5 and one with 2 element) 1 sort
3 + 2 = 5 elements 1 sort
Total count: 5 + 3 + 1 + 1 + 1 = 11 sort