Вопросы Теги

Разработайте эффективный алгоритм для сортировки 5 отличных ключей меньше чем в 8 сравнениях

В зависимости от вашей конкретной цели существует способ достижения полезности родительского селектора без использования одного (даже если бы он существовал) ...

Скажем, у нас есть: 

<div>
  <ul>
    <li><a>Pants</a></li>
    <li><a>Socks</a></li>
    <ul>
      <li><a>White socks</a></li>
      <li><a>Blue socks</a></li>
    </ul>
  </ul>
</div>

Что мы можем сделать, чтобы блок Socks (включая цвета носка) выделялся визуально с использованием интервала?

Что было бы неплохо, но не существует: 

ul li ul:parent {
  margin-top: 15px;
  margin-bottom: 15px;
}

Что существует: 

li > a {
  margin-top: 15px;
  display: block;
}
li > a:only-child {
  margin-top: 0px;
}

Это устанавливает, что все привязные ссылки имеют верхний край 15px и сбрасывают его обратно на 0 для тех, у которых нет элементов UL (или других тегов) внутри LI.

15
задан Sinan Ünür 7 October 2009 в 23:58
поделиться

10 ответов

Сравните A с B и C с D. WLOG, предположим, что A> B и C> D. Сравните A с C. WLOG, предположим, что A> C. Отсортируйте E в ACD. Это можно сделать с помощью двух сравнений. Отсортируйте B по {E, C, D}. Это можно сделать с помощью двух сравнений, всего семь.

34
ответ дан 30 November 2019 в 23:50
поделиться

Вот реализация C++ который виды 5 элементов в < = 7 сравнений. Смог найти 8 случаев, которые могут быть отсортированы в 6 сравнениях. Это имеет смысл, если мы вообразим полное двоичное дерево с 120 вершинами, то будет 112 узлов в вершинах уровня 7 и 8 на уровне 6. Вот полный код, который тестируется для работы на все возможные перестановки. 

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <numeric>

using namespace std;

ostream& operator << ( ostream& os, vector<int> v )
{
    cout << "[ ";
    for ( auto x: v ) cout << x << ' ';
    cout << "]";
    return os;
}

class Comp {
    int count;
public:
    Comp(): count{0}{}
    bool isLess( vector<int> v, int i, int j ) {
        count++;
        //cout << v << "Comparison#" << count << ": " << i << ", " << j << endl;
        return v[ i ] < v[ j ];
    }
    int getCount() { return count; }
};


int mySort( vector<int> &v )
{
    Comp c;
    if ( c.isLess( v, 1, 0 ) ) {
        swap( v[ 0 ], v[ 1 ] );
    }
    if ( c.isLess( v, 3, 2 ) ) {
        swap( v[ 2 ], v[ 3 ] );
    }
    // By now (0, 1) (2, 3) (4)
    if ( c.isLess( v, 0, 2 ) ) {
        // ( 0, 2, 3 ) (1)
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 2 ], v[ 3 ] );
    } else {
        // ( 2, 0, 1 ) ( 3 )
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 0 ], v[ 1 ] );
    }
    // By now sorted order ( 0, 1, 2 ) ( 3 ) ( 4 ) and know that 3 > 0
    if ( c.isLess( v, 4, 1 ) ) {
        if ( c.isLess( v, 4, 0 ) ) {
            // ( 4, 0, 1, 2 ) ( 3 ) ( ... )
            v.insert( v.begin(), v[4] );
            // By now ( 0, 1, 2, 3 ) ( 4 ) ( ... ) and know that 4 > 1
            if ( c.isLess( v, 4, 2 ) ) {
                // ( 0, 1, 4, 2, 3 ) ( ... )
                v.insert( v.begin() + 2, v[4] );
            } else {
                if ( c.isLess( v, 4, 3 ) ) {
                    // ( 0, 1, 2, 4, 3 ) ( ... )
                    v.insert( v.begin() + 3, v[4] );
                } else {
                    // ( 0, 1, 2, 3, 4 ) ( ... )
                    v.insert( v.begin() + 4, v[4] );
                }
            }
            // ( 1 2 3 4 5 ) and trim the rest
            v.erase( v.begin()+5, v.end() );
            return c.getCount(); /////////// <--- Special case we could been done in 6 comparisons
        } else {
            // ( 0, 4, 1, 2 ) ( 3 ) ( ... ) 
            v.insert( v.begin() + 1, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 2 ) ) {
            // ( 0, 1, 4, 2 ) ( 3 ) ( ... )
            v.insert( v.begin() + 2, v[4] );
        } else {
            // ( 0, 1, 2, 4 ) ( 3 ) ( ... )
            v.insert( v.begin() + 3, v[4] );
        }
    }
    // By now ( 0, 1, 2, 3 ) ( 4 )( ... ): with 4 > 0
    if ( c.isLess( v, 4, 2 ) ) {
        if ( c.isLess( v, 4, 1 ) ) {
            // ( 0, 4, 1, 2, 3 )( ... )
            v.insert( v.begin() + 1, v[4] );
        } else {
            // ( 0, 1, 4, 2, 3 )( ... )
            v.insert( v.begin() + 2, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 3 ) ) {
            // ( 0, 1, 2, 4, 3 )( ... )
            v.insert( v.begin() + 3, v[4] );
        } else {
            // ( 0, 1, 2, 3, 4 )( ... )
            v.insert( v.begin() + 4, v[4] );
        }
    }
    v.erase( v.begin()+5, v.end() );
    return c.getCount();
}

#define TEST_ALL
//#define TEST_ONE

int main()
{
#ifdef TEST_ALL
    vector<int> v1(5);
    iota( v1.begin(), v1.end(), 1 );
    do {
        vector<int> v2 = v1, v3 = v1;
        int count = mySort( v2 );
        if ( count == 6 )
            cout << v3 << " => " << v2 << " #" << count << endl;
    } while( next_permutation( v1.begin(), v1.end() ) );
#endif

#ifdef TEST_ONE
    vector<int> v{ 1, 2, 3, 1, 2};
    mySort( v );
    cout << v << endl;
#endif
}
0
ответ дан 30 November 2019 в 23:50
поделиться

Это псевдокод, основанный на ответе Беты. Могут быть некоторые ошибки, поскольку я сделал это в спешке. 

if (A > B)
    swap A, B
if (C > D)
    swap C, D
if (A > C)
    swap A, C
    swap B, D  # Thanks Deqing!

if (E > C)
    if (E > D) %A C D E
        if (B > D)
            if (B > E)
                return (A, C, D, E, B)
            else
                return (A, C, D, B, E)
         else
            if (B < C)
                return (A, B, C, D, E)
            else
                return (A, C, B, D, E)

    else %A C E D
        if (B > E)
            if (B > D)
                return (A, C, E, D, B)
            else
                return (A, C, E, B, D)
         else
            if (B < C)
                return (A, B, C, E, D)
            else
                return (A, C, B, E, D)
else
    if (E < A) % E A C D
        if (B > C)
            if (B > D)
                return (E, A, C, D, B)
            else
                return (E, A, C, B, D)
         else
             return (E, A, B, C, D)

    else %A E C D
        if (B > C)
            if (B > D)
                return (A, E, C, D, B)
            else
                return (A, E, C, B, D)
         else
            if (B < E)
                return (A, B, E, C, D)
            else
                return (A, E, B, C, D)
19
ответ дан 30 November 2019 в 23:50
поделиться

Должно быть 7 или более сравнений.

Есть 120 (5 факториальных) способов упорядочения 5 объектов. Алгоритм, использующий 6 сравнений, может различать только 2 ^ 6 = 64 различных начальных расположения, поэтому алгоритмы, использующие 6 или меньше сравнений, не могут отсортировать все возможные входные данные.

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

7
ответ дан 30 November 2019 в 23:50
поделиться

Согласно Википедия :

Определение точного числа сравнений, необходимых для сортировки заданного числа записей, является сложной вычислительной задачей даже для малых n, и непростой формула решения известна ».

Предположительно это означает, что не существует известного поддающегося обработке (эффективного) алгоритма для определения точно оптимальной сортировки сравнения.

3
ответ дан 30 November 2019 в 23:50
поделиться

Пример последовательности операций с использованием сортировки слиянием (функция merge ниже объединит два отсортированных подсписка в один отсортированный объединенный список): 

elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison
elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison
elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons
elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons
1
ответ дан 30 November 2019 в 23:50
поделиться

Пять элементов можно отсортировать с помощью семи сравнений в наихудшем приведении, потому что log 2 (5!) = 6.9. Я предлагаю проверить, достигает ли какой-либо стандартный алгоритм сортировки этого числа - в противном случае, должно быть довольно легко жестко закодировать последовательность сравнения из-за небольшого количества требуемых сравнений.

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

Я написал небольшую программу, чтобы сделать это, и вот результат. 

Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60
Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison
Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison
Comparison 4: 2-4 [8|7]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-3 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 3-4 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 5: 0-3 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison
Comparison 4: 3-4 [8|7]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-4 [4|3]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 4: 0-4 [8|7]
Comparison 5: 1-4 [4|4]
Comparison 6: 1-2 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 2-4 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 5: 0-2 [4|3]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison
Comparison 3: 0-3 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-2 [3|4]
Comparison 6: 2-4 [2|1]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 2-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 4: 3-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [1|2]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 2-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 3: 0-2 [15|15]
Comparison 4: 0-4 [7|8]
Comparison 5: 0-3 [3|4]
Comparison 6: 2-4 [1|2]
Comparison 7: 3-4 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 5: 1-4 [4|4]
Comparison 6: 3-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 4: 2-4 [7|8]
Comparison 5: 0-4 [3|4]
Comparison 6: 1-2 [2|1]
Comparison 7: 1-3 [1|1]
Comparison 6: 1-2 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 5: 3-4 [4|4]
Comparison 6: 1-4 [2|2]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 6: 1-3 [2|2]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]

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

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

Comparison 1: 0-1 [60|60]

Comparison 2: 2-3 [30|30]
Comparison 2: 2-3 [30|30]

Comparison 3: 0-2 [15|15]
Comparison 3: 0-3 [15|15]
-----
Comparison 3: 0-3 [15|15]
Comparison 3: 0-2 [15|15]

Comparison 4: 2-4 [8|7]
Comparison 4: 0-4 [8|7]
Comparison 4: 3-4 [8|7]
Comparison 4: 0-4 [8|7]
-----
Comparison 4: 0-4 [7|8]
Comparison 4: 3-4 [7|8]
Comparison 4: 0-4 [7|8]
Comparison 4: 2-4 [7|8]

Comparison 5: 3-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-3 [4|3]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-4 [4|3]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-2 [4|3]
-----
Comparison 5: 0-2 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 2-4 [4|4]
Comparison 5: 0-3 [3|4]
Comparison 5: 1-4 [4|4]
Comparison 5: 0-4 [3|4]
Comparison 5: 3-4 [4|4]

Comparison 6: 1-3 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [1|2]
-----
Comparison 6: 2-4 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 2-4 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-2 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 2-4 [1|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 3-4 [2|2]
Comparison 6: 1-3 [2|2]
Comparison 6: 1-2 [2|1]
Comparison 6: 1-2 [2|2]
Comparison 6: 1-4 [2|2]
Comparison 6: 1-3 [2|2]

Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
-----
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 0-2 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 2-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 0-3 [1|1]
Comparison 7: 3-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-3 [1|1]
Comparison 7: 1-2 [1|1]
Comparison 7: 1-4 [1|1]
Comparison 7: 1-2 [1|1]
7
ответ дан 30 November 2019 в 23:50
поделиться

Другие заявили, что их 5! = 120 аранжировок (перестановок) для обработки, поэтому вам нужно 7 сравнений. В принципе, чтобы идентифицировать перестановку, вы можете построить большой вложенный оператор if с глубиной 7 сравнений. После идентификации перестановки может быть применена предварительно вычисленная последовательность обмена / вращения.

Первая проблема состоит в том, что выбор второго сравнения зависит от результата первого сравнения и так далее. Уловка на каждом этапе состоит в том, чтобы выбрать хорошее сравнение, чтобы разделить текущий набор возможных перестановок на два равных подмножества. Самый простой подход - оцените разделение, которое будет достигнуто при каждом сравнении, пока не найдете достаточно сбалансированное. Если вы найдете идеальный баланс, выходите раньше, но имейте в виду, что идеальный баланс не всегда возможен, как мы. t имеет ровно 2 ^ 7 = 128 перестановок - в некоторых (я предполагаю 8) случаев нам нужно только шесть сравнений.

Вторая проблема заключается в разработке последовательностей перестановки / вращения для каждой из 120 возможных перестановок, и это, вероятно, вещь динамического программирования. Вероятно, требуется рекурсивный поиск if-I-do-this, следующий результат - это, затем рекурсивное "дерево игры", и вы действительно должны кэшировать промежуточные результаты IOW. Слишком устал, чтобы разбираться в деталях. Банкомат, извините.

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

Оберните это в генераторе кода, и все готово - ваш собственный алгоритмически почти идеальный сортировщик по 5 элементам.

1
ответ дан 30 November 2019 в 23:50
поделиться 

A B C D E

A
| C D E     - 1 Comparison
B

A C
| | E       - 1 Comparison
B D

  A
 / \
B   C   E   - 1 Comparison
     \
      D

E требуется 3 сравнения. Его следует сравнить с A , C , D

Попробуйте ACDE в указанном порядке.

Всего будет девять сравнений - - не очень производительный.

1
ответ дан 30 November 2019 в 23:50
поделиться

Сортировочная сеть с иметь ограниченную структуру, так что не отвечайте на исходный вопрос; но они забавны.
Список сортировочных сетей генерирует красивые диаграммы или списки SWAP для 32 входов. Для 5 он дает 

There are 9 comparators in this network, grouped into 6 parallel operations.  
[[0,1],[3,4]]  
[[2,4]]  
[[2,3],[1,4]]  
[[0,3]]  
[[0,2],[1,3]]  
[[1,2]]
3
ответ дан 30 November 2019 в 23:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: