Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
1

Распечатать все перестановки из N цифр

16.05.2016, 16:44. Показов 2543. Ответов 17
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задача такая. Допустим для простоты дано 5 цифр.
Причем цифры могут быть и одинаковые, например 77777
Требуется распечатать все перестановки из этих цифр.
(В приведенном примере только одна перестановка 77777)
Решение.
Для числа 5 это конечно можно решить. Всего максимум
5! = 120 вариантов. Можно перебрать все варианты и в
случае с равными цифрами просто выбросить лишнее.
Может существует алгоритм, который не создает "лишние"
перестановки? Ну рекурсивный что-ли? В общем не знаю.
Буду рад любым предложениям на сей счет.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.05.2016, 16:44
Ответы с готовыми решениями:

Найти все возможные перестановки цифр
дано 6-розрядное число...надо найти все возможные перестановки цыфр...как ето...

Распечатать все перестановки используя рекурсию (2)
Полгода назад я создавал тему с точно таким названием На этот раз задача сложнее ранее...

Распечатать все перестановки используя рекурсию
Есть проблема. Даны числа 1, 2, ... n Надо написать рекурсивную процедуру, которая распечатает ...

Вывести все возможные перестановки N заданных цифр, формируя при этом последовательность из K цифр
Дана задача: Вывести все возможные перестановки N заданных цифр формируя при этом...

17
Модератор
Эксперт функциональных языков программирования
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
16.05.2016, 17:46 2
Для начала напишем простую перестановку (все элементы разные):
Haskell
1
2
3
4
5
perm []     = [[]]
perm (x:xs) = concat $ map (allpos x) (perm xs)
 
allpos y []     = [[y]]
allpos y (x:xs) = (y:x:xs) : (map (x:) $ allpos y xs)
Чтобы получить все перестановки для непустого списка, надо добавить голову списка на все позиции в каждую из перестановок хвоста.

Функция allpos elem list добавляет elem в list на каждую из позиций (то есть, возвращает список списков). Например, allpos 'a' "bc" вернёт ["abc","bac","bca"]

Если у нас возможны одинаковые элементы, то нужно elem вставлять только на позиции впереди любого другого элемента с таким же значением.
Например, allpos2 'a' "bac" вернёт ["abac","baac"]

Сама функция perm остаётся такой же, только allpos заменяем на allpos2:
Haskell
1
2
3
4
5
6
7
allpos2 y []     = [[y]]
allpos2 y (x:xs) 
    | y == x     = [y:x:xs]
    | otherwise  = (y:x:xs) : (map (x:) $ allpos2 y xs)
 
perm2 []     = [[]]
perm2 (x:xs) = concat $ map (allpos2 x) (perm2 xs)
1
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
16.05.2016, 18:02 3
Пример на Js
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [1,2,3,4,5];
function combinator(matrix){
  return matrix.reduceRight(function(combination, x){
    var result = [];
    x.forEach(function(a){
      combination.forEach(function(b){
        result.push( [ a ].concat( b ) );
      });
    });
    return result;
  });
};
 
console.log( combinator([ arr, arr, arr, arr, arr ] ).length);
вариантов - 3125
или я не правильно понял суть задачи
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
16.05.2016, 18:11  [ТС] 4
Shamil1
Спасибо! Однако мудрёно очень!
Не могли бы Вы привести ваши рассуждения на
простом примере, скажем 1122?

Добавлено через 4 минуты
Poznakomlus
Это же перестановки! Для пяти элементов не может
быть более 5!=120 вариантов.
Вот простой пример (для пяти цифр)
11117
11171
11711
17111
71111
Все! Иного не дано!
0
Модератор
Эксперт функциональных языков программирования
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
16.05.2016, 18:46 5
Лучший ответ Сообщение было отмечено echs как решение

Решение

Цитата Сообщение от geh Посмотреть сообщение
Не могли бы Вы привести ваши рассуждения на
простом примере, скажем 1122?
Начинаем с конца.

1. Последняя цифра '2'
Все перестановки числа "2": ["2"]. (всего одна перестановка)

2. Следующая цифра '2'.
Во все числа из п.1 (их - одно) добавляем цифру '2' на все позиции... с одним запретом: нельзя ставить нашу цифру '2' правее цифры '2', если в числе встретится цифра '2'.
Все варианты добавления цифры '2' к числу "2": ["22"]
Объединяем все списки: ["22"]

3. Следующая цифра '1'.
Во все числа из п.2 (их - одно) добавляем цифру '1' на все позиции... с одним запретом: нельзя ставить нашу цифру '1' правее цифры '1', если в числе встретится цифра '1'.
Все варианты добавления цифры '1' к числу "22": ["122", "212", "221"]
Объединяем все списки: ["122", "212", "221"]

4. Следующая цифра '1'.
Во все числа из п.3 (их - три) добавляем цифру '1' на все позиции... с одним запретом: нельзя ставить нашу цифру '1' правее цифры '1', если в числе встретится цифра '1'.
Все варианты добавления цифры '1' к числу "122": ["1122"]
Все варианты добавления цифры '1' к числу "212": ["1212","2112"]
Все варианты добавления цифры '1' к числу "221": ["1221","2121","2211"]
Объединяем все списки: ["1122","1212","2112","1221","2121","2211"]
2
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
16.05.2016, 18:49  [ТС] 6
Shamil1
Я тут подумал вот о чем. Пусть дано число
11355
Нельзя ли так организовать перестановку цифр, чтобы
это число каждый раз увеличивалось до максимума
55311. И тем самым избежать повторений?

Добавлено через 2 минуты
Shamil1
Вы гений! Спасибо!
0
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
16.05.2016, 21:04 7
Цитата Сообщение от Poznakomlus Посмотреть сообщение
вариантов - 3125
это у вас 5^5 получилось, видимо вы посчитали количество Размещений с возвращениями, т.е. учитывали, что каждой цифры ограниченное количество

geh, можно смотреть на набор чисел 11355 как на набор 3-х видов элементов (единицы, тройки, пятёрки), причем единиц и пятёрок по 2 и одна тройка
И используем рекурсивный алгоритм
1. Цикл: выбираем один из имеющихся видов, количество которых ещё не кончилось
1.1. ставим выбранное число в текущую позицию
1.2. если позиция последняя, выводим новую комбинацию и выходим из цикла (других свободных чисел у нас не будет)
1.3. иначе уменьшаем количество чисел выбранного вида
1.4. переходим на новый уровень рекурсии, выполняя этот алгоритм с увеличенной на единицу позицией
1.5. возвращаем количество чисел выбранного вида и продолжаем цикл
0
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
16.05.2016, 22:08 8
Цитата Сообщение от geh Посмотреть сообщение
Вот простой пример (для пяти цифр)
здесь длина 5, а цифр - 2 (1,7)
неудачный пример. так как достаточно пройти циклом по 5 массивам и заменить одну позицию
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
function mutation(def, move, len){
  var result = [], arr = Array(len), tmp;
  for (var i = 0; i < len; i++) arr[i] = def;
  while (len--) {
    tmp = arr.slice();
    tmp[len] = move;
    result.push(tmp);
  }
  return result;
}
 
 
console.log(mutation(1, 7, 5));
0
Модератор
Эксперт функциональных языков программирования
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
17.05.2016, 00:23 9
Цитата Сообщение от Poznakomlus Посмотреть сообщение
здесь длина 5, а цифр - 2 (1,7)
неудачный пример. так как достаточно пройти циклом по 5 массивам и заменить одну позицию
нужен код, который будет работать и для двух и для пяти цифр, а не только для двух

Добавлено через 2 минуты
Цитата Сообщение от ProgJ Посмотреть сообщение
выбираем один из имеющихся видов
как выбираем?
0
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
17.05.2016, 01:28 10
Цитата Сообщение от Shamil1 Посмотреть сообщение
нужен код, который будет работать и для двух и для пяти цифр, а не только для двух
вариант, прямой перебор
Javascript
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
Array.prototype.uniq = function () {
  for (var tmp = {}, len = this.length; len--; tmp[this[len]] = 1);
  return Object.keys(tmp);
};
 
function combinator(arr, len, data){
  var count = arr.length, tmp = [], tmpArr;
  data = data || arr;
  if(--len === 0){
    return data;
  }
  data.forEach(function(val){
    arr.forEach(function(v){
      tmpArr = [ v ].concat( val );
      len === 1
      ? (tmpArr.uniq().length === count && tmp.push(tmpArr))
      : tmp.push(tmpArr);
    });
  });
  return combinator(arr, len, tmp);
};
 
var arr = [1,2,3,4,5];
var result = combinator(arr, 5);
console.log(result.length); //120
console.dir(result);
0
Модератор
Эксперт функциональных языков программирования
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
17.05.2016, 01:34 11
Цитата Сообщение от Poznakomlus Посмотреть сообщение
var arr = [1,2,3,4,5];
Теперь заменяем на [1,2,3,4,4], и программа перестаёт работать.
0
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
17.05.2016, 01:42 12
[1,2,3,4,4] так ничего же не мешает данную операцию с индексами проводить
0
Модератор
Эксперт функциональных языков программирования
3079 / 2228 / 462
Регистрация: 26.03.2015
Сообщений: 8,647
17.05.2016, 01:58 13
Цитата Сообщение от Poznakomlus Посмотреть сообщение
[1,2,3,4,4] так ничего же не мешает данную операцию с индексами проводить
тогда опять получится 120, а должно получиться 60
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
17.05.2016, 08:44  [ТС] 14
Shamil1
Я нашел еще один довольно забавный алгоритм решения
этой задачи. Пример 13335. Надо это число (в цикле)
увеличивать на 1 до 53331. И проверять есть ли в этом
числе заданные цифры. Конечно это не практично, но
алгоритм очень простой. Он существует. И я считаю своим
долгом поделиться им с вами. Может он еще Вам пригодиться!

Добавлено через 3 минуты
Shamil1
Этот алгоритм можно усовершенствовать, если использовать
только заданные цифры...
0
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
17.05.2016, 09:15 15
Цитата Сообщение от Shamil1 Посмотреть сообщение
как выбираем?
в цикле, по очереди, перебираем
0
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
17.05.2016, 16:57 16
Вариант решения Js
Javascript
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
30
let mutation = (arr, len)=> {
  let table = {}, temp = [],
    uniqAndHashTable = arr=> {
      return arr.filter((a)=> {
        table[a] = ++table[a] || 1;
        return table[a] === 1;
      });
    },
    limit = (data, value)=> {
      return table[value] === data.reduce((previous, current) => {
          return previous += current === value ? 1 : 0;
        }, 0);
    };
  arr = uniqAndHashTable(arr);
  while (len--) temp[len] = arr;
  return temp.reduce((previous, current)=> {
    let result = [];
    current.forEach((a)=> {
      previous.forEach((b)=> {
        if ((Array.isArray(b) && limit(b, a)) || (a === b && table[a] === 1)) return true;
        result.push([a].concat(b));
      });
    });
    return result;
  });
};
 
console.dir(mutation([1, 2, 3, 4, 4], 4));
console.log(mutation([1, 2, 3, 4, 4], 5).length); //60
console.log(mutation([1, 2, 3, 4, 5], 5).length); //120
Песочница
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
17.05.2016, 17:14  [ТС] 17
Poznakomlus
Спасибо! Но я этот язык к сожалению не знаю.
Не могли бы вы на примере пояснить его алгоритм?
0
Эксперт PHP
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
18.05.2016, 01:10 18
Вариант решения Php
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private function build()
    {
        $this->result = array_reduce(array_fill(0, $this->len - 1, $this->arr), function ($previous, $current) {
            $result = [];
            foreach ($current as $a) {
                foreach ($previous as $b) {
                    if (is_array($b)) {
                        $values = array_count_values($b);
                        if (empty($values[$a]) || $this->table[$a] > $values[$a]) {
                            $result[] = array_merge([$a], $b);
                        }
                    } elseif ($a !== $b || $this->table[$a] > 1) {
                        $result[] = array_merge([$a], [$b]);
                    }
                }
            }
 
            return $result;
        }, $this->arr);
 
    }
песочница
алгоритм таков
берем массив, создаем таблицу количества оригинальных символов массива
далее делаем этот массив уникальным
создаем массив из этих уникальных массивов и нашей длиной
запускаем reduce функцию в ней два for в результате фильтруем, чтоб не добавить одинаковых символов сверяясь с таблицой table
Объяснил как смог
1
18.05.2016, 01:10
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
18.05.2016, 01:10
Помогаю со студенческими работами здесь

Получить все перестановки из цифр 1, 2, 3, 4
условие такое: Получить все перестановки из цифр 1, 2, 3, 4. Отсортировать их как десятичные...

Получить все перестановки из цифр 1, 2, 3, 4
Получить все перестановки из цифр 1, 2, 3, 4. Отсортировать их как десятичные числа по убыванию.

Среди цифр введенной строки распечатать ту, которая появлялась чаще других. Если таких цифр было несколько, распечатать ту, что встречалась первой
Среди цифр введенной строки распечатать ту, которая появлялась чаще других. Если таких цифр было...

Вывести все варианты перестановки цифр числа
Есть программа которая выводит на экран все варианты перестановки чисел 01234567. Помогите...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Новые блоги и статьи
Что такое хорошо и что такое плохо, вид сбоку. Индивид и общество - грань не нарушения.
Hrethgir 18.01.2025
В моей личной жизни и времени, я рассуждаю категорией "хуже-лучше", в том плане, когда меня спросили например - "а зачем ты делаешь свой процессор?", то я ответил - "чтобы сделать свою жизнь лучше". . .
Передача по ссылке или по значению в Java?
InfoMaster 18.01.2025
В мире программирования на Java одним из ключевых аспектов, требующих глубокого понимания, является механизм передачи параметров в методы. Этот фундаментальный концепт часто становится источником. . .
Тернарный условный оператор в Python
InfoMaster 18.01.2025
В мире программирования существует множество инструментов и конструкций, позволяющих создавать эффективный и лаконичный код. Одним из таких инструментов является тернарный условный оператор, который. . .
Как удалить неотслеживаемые файлы из рабочего дерева Git
InfoMaster 18.01.2025
В процессе разработки программного обеспечения с использованием системы контроля версий Git часто возникает необходимость в управлении неотслеживаемыми файлами. Неотслеживаемые файлы (untracked. . .
Что делает код if __name__ == "__main__": в Python
InfoMaster 18.01.2025
В мире программирования на Python существует множество важных концепций, и одной из наиболее интересных является конструкция if __name__ == "__main__". Эта специальная конструкция играет ключевую. . .
Как заставить Git забыть об отслеживаемом файле, добавленном в .gitignore
InfoMaster 18.01.2025
В мире разработки программного обеспечения система контроля версий Git стала неотъемлемой частью рабочего процесса, позволяя эффективно отслеживать изменения в коде и управлять ими. Однако. . .
Что означает use strict в JavaScript и для чего используется
InfoMaster 18.01.2025
В мире современной веб-разработки JavaScript играет ключевую роль как один из основных языков программирования. По мере его эволюции возникла необходимость в механизмах, которые помогли бы. . .
Как работать со скрытыми (hidden) элементами в jQuery
InfoMaster 18.01.2025
В современной веб-разработке управление видимостью элементов на странице является одним из ключевых аспектов создания интерактивных пользовательских интерфейсов. jQuery предоставляет мощный набор. . .
Как переключаться между ветками (Branch) с помощью checkout в Git
InfoMaster 18.01.2025
Ветки в Git являются одной из ключевых концепций для управления версионностью кода, позволяя разработчикам эффективно работать в команде и параллельно развивать программные проекты. Каждый новый. . .
Что такое стек и куча, чем они отличаются и где находятся
InfoMaster 18.01.2025
Понимание основных концепций памяти в программировании В мире современного программирования эффективное управление памятью играет ключевую роль в создании производительных и надежных приложений. . . .
Как использовать комментарии в JSON
InfoMaster 18.01.2025
JSON (JavaScript Object Notation) представляет собой легкий и широко используемый формат обмена данными, который стал стандартом де-факто для веб-приложений и программных интерфейсов. При работе с. . .
Как заставить git pull перезаписать локальные файлы в Git
InfoMaster 18.01.2025
Проблема перезаписи локальных файлов в Git При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо синхронизировать локальный репозиторий с. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru