모든 순열을 통해 한 번에 하나의 스왑을 밟습니다

Question

n 개의 고유 한 항목 목록이 주어지면 한 번에 한 쌍의 값 만 교체하는 항목의 각 순열을 어떻게 진행할 수 있습니까? (가능하다고 생각합니다. 확실히해야한다고 생각합니다.)

내가 찾고있는 것은 반복 된 항목 쌍의 지수를 스왑 할 반복자입니다. 목록의 순서가 순서대로. 다시 한 번 반복하면 목록을 보너스가 될 시작 순서로 복원하지만 요구 사항은 아닙니다. 모든 쌍이 첫 번째 (마지막) 요소가 쌍 중 하나로 포함되므로 함수는 단일 값 만 반환하면 보너스입니다.

예 :-3 가지 요소의 경우, 첫 번째 요소를 첫 번째 및 두 번째 요소로 교체하여 순열을 통해 반복 할 수 있습니다 : (ABC) 스왑 0-2 => (CBA) 1-2 (CAB) 0-2 ( BAC) 1-2 (BCA) 0-2 (ACB).

나는 C로 구현할 것이지만 아마도 대부분의 언어로 솔루션을 퍼즐로 만들 수 있습니다.

Answer 1

아, n = 4에 대한 시퀀스를 계산하면 ( "항상 첫 번째 항목을 다른"다른 "제약 조건으로 바꾸면) 시퀀스를 찾을 수있었습니다. A123400 OEIS에서 "Ehrlich의 스왑 방법"이 필요하다고 말했습니다.

구글이 나를 찾았다 C ++ 구현, 나는 내가 가정합니다 이것 GPL 아래에 있습니다. 나는 또한 Knuth를 찾았습니다 Fascicle 2B 정확히 내 문제에 대한 다양한 솔루션을 설명합니다.

테스트 된 C 구현이 있으면 코드로 업데이트하겠습니다.

다음은 Knuth의 설명을 기반으로 Ehrlich의 방법을 구현하는 일부 Perl 코드입니다. 최대 10 개의 항목의 목록의 경우 각 경우에 전체 순열 목록을 올바르게 생성 한 다음 중지 한 것을 테스트했습니다.

#
# Given a count of items in a list, returns an iterator that yields the index
# of the item with which the zeroth item should be swapped to generate a new
# permutation. Returns undef when all permutations have been generated.
#
# Assumes all items are distinct; requires a positive integer for the count.
#
sub perm_iterator {
    my $n = shift;
    my @b = (0 .. $n - 1);
    my @c = (undef, (0) x $n);
    my $k;
    return sub {
        $k = 1;
        $c[$k++] = 0 while $c[$k] == $k;
        return undef if $k == $n;
        ++$c[$k];
        @b[1 .. $k - 1] = reverse @b[1 .. $k - 1];
        return $b[$k];
    };
}

예제 사용 :

#!/usr/bin/perl -w
use strict;
my @items = @ARGV;
my $iterator = perm_iterator(scalar @items);
print "Starting permutation: @items\n";
while (my $swap = $iterator->()) {
    @items[0, $swap] = @items[$swap, 0];
    print "Next permutation: @items\n";
}
print "All permutations traversed.\n";
exit 0;

요청에 따라 파이썬 코드. (죄송합니다. 아마도 관용적으로 관용적이지 않을 것입니다. 개선에 대한 제안을 환영합니다.)

class ehrlich_iter:
  def __init__(self, n):
    self.n = n
    self.b = range(0, n)
    self.c = [0] * (n + 1)

  def __iter__(self):
    return self

  def next(self):
    k = 1
    while self.c[k] == k:
      self.c[k] = 0
      k += 1
    if k == self.n:
      raise StopIteration
    self.c[k] += 1
    self.b[1:k - 1].reverse
    return self.b[k]

mylist = [ 1, 2, 3, 4 ]   # test it
print "Starting permutation: ", mylist
for v in ehrlich_iter(len(mylist)):
  mylist[0], mylist[v] = mylist[v], mylist[0]
  print "Next permutation: ", mylist
print "All permutations traversed."

Answer 2

나는 그것이 당신에게 너무 늦었을 것이라고 확신하지만, 나는이 질문에 좋은 추가를 발견했다. Steinhaus – Johnson – Trotter 알고리즘 그리고 그 변형은 당신이 요구 한 것을 정확하게합니다. 또한 항상 인접한 지수를 교환하는 추가 특성이 있습니다. 나는 Java에서 반복자로 변형 (심지어) 중 하나를 구현하려고 노력했으며 잘 작동합니다.

import java.util.*;

// Based on https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm#Even.27s_speedup
public class PermIterator
    implements Iterator<int[]>
{
    private int[] next = null;

    private final int n;
    private int[] perm;
    private int[] dirs;

    public PermIterator(int size) {
        n = size;
        if (n <= 0) {
            perm = (dirs = null);
        } else {
            perm = new int[n];
            dirs = new int[n];
            for(int i = 0; i < n; i++) {
                perm[i] = i;
                dirs[i] = -1;
            }
            dirs[0] = 0;
        }

        next = perm;
    }

    @Override
    public int[] next() {
        int[] r = makeNext();
        next = null;
        return r;
    }

    @Override
    public boolean hasNext() {
        return (makeNext() != null);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    private int[] makeNext() {
        if (next != null)
            return next;
        if (perm == null)
            return null;

        // find the largest element with != 0 direction
        int i = -1, e = -1;
        for(int j = 0; j < n; j++)
            if ((dirs[j] != 0) && (perm[j] > e)) {
                e = perm[j];
                i = j;
            }

        if (i == -1) // no such element -> no more premutations
            return (next = (perm = (dirs = null))); // no more permutations

        // swap with the element in its direction
        int k = i + dirs[i];
        swap(i, k, dirs);
        swap(i, k, perm);
        // if it's at the start/end or the next element in the direction
        // is greater, reset its direction.
        if ((k == 0) || (k == n-1) || (perm[k + dirs[k]] > e))
            dirs[k] = 0;

        // set directions to all greater elements
        for(int j = 0; j < n; j++)
            if (perm[j] > e)
                dirs[j] = (j < k) ? +1 : -1;

        return (next = perm);
    }

    protected static void swap(int i, int j, int[] arr) {
        int v = arr[i];
        arr[i] = arr[j];
        arr[j] = v;
    }


    // -----------------------------------------------------------------
    // Testing code:

    public static void main(String argv[]) {
        String s = argv[0];
        for(Iterator<int[]> it = new PermIterator(s.length()); it.hasNext(); ) {
            print(s, it.next());
        }
    }

    protected static void print(String s, int[] perm) {
        for(int j = 0; j < perm.length; j++)
            System.out.print(s.charAt(perm[j]));
        System.out.println();
    }
}

끝에서 사이클을 다시 시작하는 무한 반복기 또는 다음 순열 대신 교환 지수를 반환하는 반복자로 쉽게 수정할 수 있습니다.

여기 다양한 구현을 수집하는 또 다른 링크.

Answer 3

C ++ 표준 라이브러리 기능 Next_PerMuation (...)을 살펴보십시오. 좋은 출발점이되어야합니다.

Answer 4

당신은 볼 수 있습니다 https://sourceforge.net/projects/swappermutation/ 이는 정확한 귀하의 요구 사항을 Java 구현으로 스왑을 생성하는 반복자입니다. 얼마 전에 최근에 업데이트 된 것을 만들었습니다.