Обязательный алгоритм программиста - перестановка и комбинация

алгоритм

Обязательный алгоритм программиста - перестановка и комбинация

[TOC]

Помните перестановки?

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

    排列组合公式
    формула перестановки

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

Реализация полной перестановки

  • Насильственное решение (не рекомендуется, нецелесообразно)

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

    def force():
    data = "abc"
    for i in range(len(data)):
        for j in range(len(data)):
            for k in range(len(data)):
                if data[i] != data[j] and data[j] != data[k] and data[k] != data[i]:
                    print(data[i],data[j],data[k])

if __name__ == '__main__':
    force()
/*输出
  a b c
  a c b
  b a c
  b c a
  c a b
  c b a
*/

    Выглядит нормально, но у этого есть несколько недостатков, если вы не хотите расставлять все по местам.abc, но хочу быть правabcdВсе расстановки сделаны, тогда надо модифицировать исходный код, добавить цикл for, а если количество расстановок велико, то этого цикла слишком много.

  • Решать рекурсивно

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

    这里写图片描述
    напишите сюда описание фото

    заabcКогда мы организуем расположение, мы можем сначала рассмотреть возможные ситуации первой позиции, как показано на рисунке выше, есть три ситуации a, b и c, а затем расположить последние две, используя ту же идею, так что Мы можем легко добиться полной перестановки с помощью рекурсии.

    def rank(data, step):
    if len(data) == step+1:
        print(data)
        return
    else:
        for i in range(step, len(data)):
          data[step], data[i] = data[i], data[step]  //让当前首位依次为后面的每一个数
          rank(data, step + 1)                       //递归后面的情况
          data[step], data[i] = data[i], data[step]

if __name__ == '__main__':
    data = list("abc")
    rank(data, 0)

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

  • Решить задачу дублирования полной перестановки

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

    Чтобы решить эту задачу, нам сначала нужно узнать, откуда возникла эта проблема, или обратиться к картинке только что, мы немного модифицируем ее:

    这里写图片描述
    напишите сюда описание фото

    просто возьмиcacВот каштан:

    • Начиная с первого c, нам нужноacСделайте полную перестановку, нет проблем

    • Начиная с a, нам нужноccСделайте полную перестановку, нет проблем

    • Начиная со второго c, нам нужноcaЕсть проблема с полной аранжировкой.Полная аранжировка ac и ca не та, и начало тоже одинаковое.Это обязательно повторится.Давайте немного доработаем исходный код:

      def is_equal(data,left,right):     #判断left到当前right是否有相等的，如果有说明之前已经对这
    for i in range(left,right):       #个进行过全排序了
        if data[i] == data[right]:
            return True
    return False
def rank(data, step):
    if len(data) == step+1:
        print(data)
        return
    else:
        for i in range(step, len(data)):
            if is_equal(data,step,i):  #加一个判断
                continue
            else:
                data[step], data[i] = data[i], data[step]
                rank(data, step + 1)
                data[step], data[i] = data[i], data[step]
if __name__ == '__main__':
    data = list("bcc")
    rank(data, 0)

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

комбинаторная задача

  • описание проблемы

    чтобы присоединиться, у меня есть массив[1, 2, 3, 4, 5, 6], я хочу случайным образом выбрать три из них и спросить, какие есть методы.

  • Решения

    То же самое рекурсивно, потому что мы не знаем конкретного количества циклов, но как рекурсивно?

    这里写图片描述
    напишите сюда описание фото

    Не волнуйтесь, допустим, мы хотим выбрать 3 элемента из приведенного выше массива.

    Начнем с первого элемента.Для первого элемента у нас есть два варианта: делать или нет.

    Если это так, то нам нужно выбрать на один элемент меньше, нам нужно выбрать только два из следующих элементов.

    ​ Если нет, то продолжим рассматривать второй элемент.На этот раз нам еще предстоит выбрать три (Хотел нарисовать картинку для демонстрации, но эта картинка кажется немного сложной. Автор действительно новичок в рисовать и будет лень).

    def combine(data, step, select_data, target_num):
    if len(select_data) == target_num:   #选择的元素已经够了，就输出并返回
        print(select_data)
        return
    if step >= len(data):               #没有元素选了而且还没够，也是直接返回
        return
    select_data.append(data[step])             #选择当前元素
    combine(data, step + 1, select_data, target_num)
    select_data.pop()                         #别忘了从已选择元素中先删除
    combine(data, step + 1, select_data, target_num) #不选择当前元素
if __name__ == '__main__':
    data = [1, 2, 3, 4, 5, 6]
    combine(data, 0, [], 3)

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

Суммировать

  • Алгоритм перестановки и комбинирования все еще очень близок к нашей жизни, он часто встречается в различных алгоритмах, проектах и ​​интервью, поэтому считается обязательным алгоритмом для программистов. чтобы оставить сообщение автору.Учитесь общаться и прогрессировать вместе. Вы также можете подписаться на мой публичный аккаунт в WeChat:

    ​

Категории