Генерация перестановки с использованием одного стека - PullRequest
Новая
       23

Генерация перестановки с использованием одного стека

4 голосов
/ 25 июня 2011

Может ли кто-нибудь объяснить, какой алгоритм генерирует возможные перестановки, когда используется только один стек, а push и pop - единственные разрешенные операции.Искал об этом много, но однозначного ответа нет.Также общее количество таких перестановок дается каталонскими числами.Но я не могу получить доказательства для этого.Пожалуйста, объясните это, если это возможно.

Спасибо !!

Ответы [ 3 ]

5 голосов
/ 26 июня 2011

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

Операции: «поместить элемент из очереди ввода в стек» и «вставить элемент из стека в очередь вывода». 

                  1 2 3
output  ______   ______  input  
              \ /
        <--+   |   +---
       pop |   |   | push
           |   |   v

             stack

Например, с помощью ввода 1 2 3 вы можете получить вывод 2 1 3 в следующей последовательности:

  • толчок 1 от входа к стеку
  • толчок 2 от входа к стеку
  • pop 2 из стека в вывод
  • pop 1 из стека в вывод
  • толчок 3 от входа к стеку
  • pop 3 из стека в вывод

Но вам будет трудно, если вы попытаетесь сгенерировать 3 1 2.

Как вы генерируете все перестановки, которые возможны с этими операциями? Что ж, это просто сделать рекурсивно: в любом данном состоянии (где «состояние» состоит из содержимого входной очереди, стека и выходной очереди), можно выполнить не более двух возможных операций (вы можете нажать если есть хотя бы один элемент во входной очереди; вы можете открыть, если в стеке хотя бы один элемент), что даст вам не более двух возможных новых состояний для исследования.

Для получения более подробной информации об этой проблеме и связи с каталонскими числами, перейдите и найдите копию книги Кнута «Искусство компьютерного программирования», том 1 (3-е изд.) - это обсуждается в §2.2.1; см. упражнения 2 - 5 на стр. 242-243 (и лучшую версию моей схемы на стр. 240!).

0 голосов
/ 11 февраля 2013

Я думал об этой же проблеме и закончил тем, что написал небольшую программу на Прологе для генерации перестановок, «обнаружил» связь с каталонскими числами, а затем нашел ваш вопрос. Так что на самом деле это не ответ на ваш вопрос, а вот программа Prolog: 

% Generate permutation counts
count_pushpop(N-K) :-
    length(_, N),
    findall(Seq, pushpop(N, Seq), Seqs),
    length(Seqs, K).


% Create an integer sequence from 1 to N
% and permutate it using all possible push-pop
% operations starting with an empty stack.
pushpop(N, Seq) :-
    numlist(1, N, List),
    pushpop(List, [], Seq).


% Generate all the possible ways a list
% of items can be pushed into a stack
% and poped out of it.
pushpop([], [], []).

pushpop([H | List], Stack, Seq) :-
    pushpop(List, [H | Stack], Seq).

pushpop(List, [H | Stack], [H | Seq]) :-
    pushpop(List, Stack, Seq).

Доказательство того, что не все n! перестановки возможны: 

?- findall(Seq, pushpop(3, Seq), Seqs).
Seqs = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]].

Доказательство того, что оно генерирует каталонские числа (или это будет доказательством, если бы не переполнение стека;)): 

?- count_pushpop(N-K).
N = K, K = 0 ;
N = K, K = 1 ;
N = K, K = 2 ;
N = 3,
K = 5 ;
N = 4,
K = 14 ;
N = 5,
K = 42 ;
N = 6,
K = 132 ;
N = 7,
K = 429 ;
N = 8,
K = 1430 ;
N = 9,
K = 4862 ;
N = 10,
K = 16796 ;
N = 11,
K = 58786 ;
N = 12,
K = 208012 ;
ERROR: Out of global stack
0 голосов
/ 26 июня 2011

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

  1. Вы можете только читать со входа последовательно.

  2. Запись вывода аналогичным образом происходит последовательно, и данные, записанные в вывод, не могут быть прочитаны после записи.

  3. В дополнение к одному стеку вам разрешено только постоянное количество памяти. (Это означает отсутствие дополнительной рекурсии или структур данных).

Это следствие леммы прокачки для контекстно-свободных языков:

Вики: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

(Или также проверьте: Майкл Сипсер (1997). Введение в теорию вычислений. Я считаю, что это одно из упражнений в главе 4.)

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

def permute(seq, permutation):
    result = []
    for i in permutation:
        result.push(seq[i])
    return result

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

...