ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужен оптимальный алгоритм перестановок элементов массива
25 сообщений из 27, страница 1 из 2
  1  все
Нужен оптимальный алгоритм перестановок элементов массива
    #39354661
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
Всем добрый день.
Существует некоторый массив элементов, в котором элементы расположены так:

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 26 27 28 29

нужно за минимальное число перестановок элементов массива сделать их него вот такой массив:

1 11 21 2 12 22 3 13 23 4 14 24................................ 9 19 29

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

спасибо за идеи!
...
Рейтинг: 0 / 0
25.11.2016, 15:31
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354681
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тут достаточно сделать функцию сравнения двух элементов и затем сортировку с ее помощью.
...
Рейтинг: 0 / 0
25.11.2016, 16:03
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354684
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
Dima T,

для наглядности я представил данные цифрами. в реальном массиве же лежат не цифры, просто их посортировать не получится.
...
Рейтинг: 0 / 0
25.11.2016, 16:06
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354693
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
makhaonдля наглядности я представил данные цифрами. в реальном массиве же лежат не цифры, просто их посортировать не получится.
Создай еще один массив той же размерности с цифрами, отсортируй его, по нему переставляй в исходном или в новый.

 
функция сравнения
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
int compare(int a, int b) {
  int ret = 0;
  while(a != b) {
     int da = a % 10;
     int db = b % 10;
     if(da == db) {
        a = (a - da) / 10;
        b = (b - db) / 10;
     } else if (da > db) {
        ret = 1;
        break;
     } else {
        ret = -1;
        break;
     }
  }
  return ret;
}

...
Рейтинг: 0 / 0
25.11.2016, 16:17
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354711
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
Dima T,

скажем так. я могу и так узнать, как именно массив зациклен и без сортировки просто сгенерировать нужную последовательность цифр. самый главный вопрос: переставлять потом как?

1. не переставляем.
2. переставляем с 11? потом как мне 2-ку на место (4-е) поставить? :)

нет проблемы с сортировкой. непонятно, как потом быстро переставить элементы.
вангую - что алгоритм элементарный, но я его не вижу.
...
Рейтинг: 0 / 0
25.11.2016, 16:39
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354727
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
makhaonглавная задача - минимизировать общее число перестановок
В таком случае:
1) Определяем элементы, которые уже на месте. Исключаем их из процесса.
2) Из оставшихся - помещаем обменом на место первый элемент. Исключаем его. Если обмененный с ним элемент попал на своё место - тоже исключаем.
3) Повторяем пункт 2, пока все элементы не окажутся на своих местах.

Фактически - жадный алгоритм. Может не найти оптимум. Но вычислительная сложность поиска оптимума стопудово перевесит его выгодность по отношению к найденному варианту.

Дополнительные элементы - не нужны. Предложенный алгоритм гарантированно на каждом шаге уменьшает число стоящих не на месте элементов на 1, а при удаче на 2. При дополнительной памяти шаги с её использованием гарантировано ставят на место не более 1 элемента, а также присутствуют шаги, когда ни один элемент не встаёт на место.
...
Рейтинг: 0 / 0
25.11.2016, 17:10
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354732
locked
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locked
Гость
makhaonDima T,

скажем так. я могу и так узнать, как именно массив зациклен и без сортировки просто сгенерировать нужную последовательность цифр. самый главный вопрос: переставлять потом как?

1. не переставляем.
2. переставляем с 11? потом как мне 2-ку на место (4-е) поставить? :)

нет проблемы с сортировкой. непонятно, как потом быстро переставить элементы.
вангую - что алгоритм элементарный, но я его не вижу.
сразу делай сортировку в нужном порядке. В qsort есть предикат сравнения. в твоем случае сравнение делается начиная с младших разрядов.
...
Рейтинг: 0 / 0
25.11.2016, 17:14
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354769
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
хеш-функция не вариант?
...
Рейтинг: 0 / 0
25.11.2016, 18:01
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354776
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Примитив в VBA по исходному условию:
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
Dim i%, hashIndex%, source, dest
source = Array(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, 26, 27, 28, 29)
ReDim dest(LBound(source) To UBound(source))
For i = LBound(source) To UBound(source)
    hashIndex = 3 * (source(i) Mod 10) + (source(i) \ 10) - 1
    dest(hashIndex) = source(i)
Next
...
Рейтинг: 0 / 0
25.11.2016, 18:12
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354833
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
Сделал, в общем, сортировкой с функцией Dima T. похоже - что всё работает, как нужно. наверно быстрее (читай - за меньшее число перестановок), чем быстрая сортировка всё равно не получится.
Всем огромное спасибо за обсуждение! Dima T - за функцию!
...
Рейтинг: 0 / 0
25.11.2016, 19:53
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354835
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
makhaon,

у членов (инстансы классов) массива добавил его порядковый номер в массиве, по ним и посортировал.
...
Рейтинг: 0 / 0
25.11.2016, 19:56
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354853
Владимир2012
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир2012
Участник
makhaonСуществует некоторый массив элементов, в котором элементы расположены так:
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 26 27 28 29
нужно за минимальное число перестановок элементов массива сделать их него вот такой массив:
1 11 21 2 12 22 3 13 23 4 14 24................................ 9 19 29Т.е. они сгруппированы по значению последней цифры в числе.
Какой-то пример приведенный вами не удачный.
Потому как исходя из конкретного вашего примера ни каких перестановок и сравнений вообще не нужно.
Пишется элементарный алгоритм, который сразу формирует массив согласно предложенного вами.

Небольшой комментарий к предлагаемому алгоритму.
Предположим у вас в исходном массиве 1000 items.
Тогда просто рассчитываем количество item у которых последняя цифра == 1 и генерируем их
/то бишь помещаем их в исходный массив сразу. Так как в алгоритме мы знаем индекс где item должен находиться/.
Впрочем предложенный способ годится и для остальных последних цифр в значениях items.

Sorry.
Реализацию алгоритма не стану приводить, так как он тривиально прост.

PS: Если бы ваш массив был не упорядоченный, то можно его упорядочить вообще не прибегая ни к каким
перестановкам ...
Но это уже другая песня ...
...
Рейтинг: 0 / 0
25.11.2016, 20:33
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354865
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Нипанимаю... зафигом нужна сортировка, когда есть алгоритм с гарантированным O(n)? просто описанный мной выше алгоритм нужно инвертировать, и выполнять обмен не по конечной, а по текущей позиции.
...
Рейтинг: 0 / 0
25.11.2016, 21:33
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39354883
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
AkinaНипанимаю...Нифиганипанимаю +1
а "патриарх "пятничных бенчмарков"" что-то скажет?
...
Рейтинг: 0 / 0
25.11.2016, 22:35
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355207
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тут нечего добавить.

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

Это мне почему-то напомнило Microsoft-овскую сортировку терабайтного текстового
файла с неизвестной длиной строки. Эффективность решения зависит от гарантий
того, какие данные придут или могут приходить на вход. Какова статистика.

А в сабжевой задаче - сбивает с толку ярко выраженная последовательность целых
чисел от 1 до 29 ? Это sequence? Так всегда будет? Тогда решение тривиально.
Это генерация новой последовательности. Про это уже писали выше.
...
Рейтинг: 0 / 0
26.11.2016, 23:00
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355272
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

Похоже, речь идет о строковой сортировке по обращенному значению строки.
Функция сравнения здесь самая необыкновенно обыкновенная, но применяется не к исходным элементам массива, а к их реверсу, если реверс выделен в отдельную функцию.
...
Рейтинг: 0 / 0
27.11.2016, 02:02
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355292
Мудроглюков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Мудроглюков
Участник
похоже на задачку с собеседования, решаемую на раз-два

числа записать инвертированными строками
лексикографически упорядочить
инвертировать (обратно)
...
Рейтинг: 0 / 0
27.11.2016, 05:12
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355409
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
В реальной задаче идет сортировка в TObjectList<T> с помощью компаратора. Функция сортировки, приведенная Dima T отлично работает.
Думаю, что существенно большего ускорения как быстрой сортировкой добиться не удастся. Разве что сразу стараться заполнять список вычисляя места данных еще до того, как они будут помещены в список. Однако - текущая скорость обработки меня более чем устраивает. Остановлюсь на это варианте.

авторЭто sequence? Так всегда будет?

Да, это последовательность. Фактически это номера инстансов в списке. Если сортировать по ним - список сортируется как нужно.
...
Рейтинг: 0 / 0
27.11.2016, 15:14
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355426
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
Мудроглюков,

авторчисла записать инвертированными строками
лексикографически упорядочить
инвертировать (обратно)

Я привел простой случай, когда массив нужно сортировать с циклом равным 10-ти, однако это не всегда так (точнее так - редкость). Цикл чисел может быть разный, например:

1 2 3 4 5 6 7 8 9 10 > 1 6 2 7 3 8 4 9 10
...
Рейтинг: 0 / 0
27.11.2016, 15:47
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355431
locked
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locked
Гость
makhaonМудроглюков,

авторчисла записать инвертированными строками
лексикографически упорядочить
инвертировать (обратно)

Я привел простой случай, когда массив нужно сортировать с циклом равным 10-ти, однако это не всегда так (точнее так - редкость). Цикл чисел может быть разный, например:
И?
Тебе уже несколько раз сказали - делаешь свой компаратор. Под свою уникальную последовательность
makhaon1 2 3 4 5 6 7 8 9 10 > 1 6 2 7 3 8 4 9 10
и в этом случае компаратор - три строчки.
...
Рейтинг: 0 / 0
27.11.2016, 16:08
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355434
locked
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
locked
Гость
makhaonВ реальной задаче идет сортировка в TObjectList<T> с помощью компаратора. Функция сортировки, приведенная Dima T отлично работает.
Думаю, что существенно большего ускорения как быстрой сортировкой добиться не удастся. Разве что сразу стараться заполнять список вычисляя места данных еще до того, как они будут помещены в список. Однако - текущая скорость обработки меня более чем устраивает. Остановлюсь на это варианте.

авторЭто sequence? Так всегда будет?

Да, это последовательность. Фактически это номера инстансов в списке. Если сортировать по ним - список сортируется как нужно.
Всегда удивляли люди использующие списки. И вдвойне - сортирующие их
...
Рейтинг: 0 / 0
27.11.2016, 16:09
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355512
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
locked,

так я и написал, что сделал компаратор :) как Dima T изначально кинул.

автори в этом случае компаратор - три строчки.

Нужен один для всех случаев. Потому как все случаи заранее неизвестны. Указанный работает в общем случае. Только вместо периода цикла (10) подставляю своё значение.
...
Рейтинг: 0 / 0
27.11.2016, 18:57
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39355515
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
locked,

авторВсегда удивляли люди использующие списки. И вдвойне - сортирующие их

Есть варианты более подходящие для хранения массива инстансов классов? Delphi, если что.
...
Рейтинг: 0 / 0
27.11.2016, 19:00
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39356970
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
makhaon,

посмотри в самом конце этой заметки http://guildalfa.ru/alsha/node/26
...
Рейтинг: 0 / 0
29.11.2016, 15:37
| Ответить | Цитировать | Написать  
Нужен оптимальный алгоритм перестановок элементов массива
    #39360772
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
makhaonВсем добрый день.
Существует некоторый массив элементов, в котором элементы расположены так:

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 26 27 28 29

нужно за минимальное число перестановок элементов массива сделать их него вот такой массив:

1 11 21 2 12 22 3 13 23 4 14 24................................ 9 19 29

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

спасибо за идеи!


А в каких позициях должны оказаться числа 10 и 20 ?
...
Рейтинг: 0 / 0
05.12.2016, 18:18
| Ответить | Цитировать | Написать  
25 сообщений из 27, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужен оптимальный алгоритм перестановок элементов массива
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39354711&tid=1340551]:
 0ms
get settings:
 12ms
get forum list:
 17ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 60ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 66ms
get tp. blocked users:
 1ms
others: 244ms
total:  419ms
созд. / загр.: 419ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]