يخطو من خلال جميع التباديل مبادلة واحدة في وقت واحد

Question

نظرا لقائمة من العناصر الناجية، كيف يمكنني الخطوة من خلال كل التقليب من العناصر التي تبادل زوج واحد فقط من القيم في وقت واحد؟ (أفترض أنه من الممكن، من المؤكد أنه يبدو أنه ينبغي أن يكون كذلك.)

ما أبحث عنه هو جهاز كمكر مائي يعطي مؤشرات الزوج التالي من العناصر إلى المبادلة، بحيث إذا تطفأ N! -1 مرات سوف تدخل N! التباديل في القائمة في بعض النظام. إذا كان تكرارها مرة أخرى ستعيد القائمة إلى أمر البدء الذي سيكون مكافأة، لكنه ليس شرطا. إذا كانت جميع الأزواج تنطوي على العنصر الأول (resp. آخر) كواحد من الزوج، بحيث تحتاج الوظيفة فقط إلى إرجاع قيمة واحدة، من شأنها أن تكون أيضا مكافأة.

مثال: - لمدة 3 عناصر، يمكنك تبديل العنصر الأخير بالتناوب مع العناصر الأولى والثانية للحلاقة من خلال التباديل، VIZ: (ABC) مبادلة 0-2 => (CBA) 1-2 (CAB) 0-2 (CAB) 0-2 (CAB) 0-2 BAC) 1-2 (BCA) 0-2 (ACB).

سأقوم بالتنفيذ في ج، ولكن ربما يمكن أن ألغى الحلول في معظم اللغات.

Answer 1

آه، بمجرد حساب تسلسل ل n = 4 (مع "تبديل دائما العنصر الأول مع قيد آخر)، كنت قادرا على العثور على تسلسل A123400. في OEIS، أخبرني أنني بحاجة إلى طريقة "مبادلة إيرليتش".

وجدت جوجل لي تنفيذ C ++, ، الذي أفترض من هذه تحت GPL. لقد وجدت أيضا نوث Fascicle 2B. الذي يصف الحلول المختلفة لمشكلتي بالضبط.

بمجرد أن يكون لدي تطبيق تم اختباره، سأقوم بتحديث هذا برمز.

إليك بعض رمز بيرل الذي ينفذ طريقة Ehrlich استنادا إلى وصف Nuth. للحصول على قوائم تصل إلى 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;

حسب الطلب، كود بيثون. (عذرا، ربما لا يكون oriomatic. اقتراحات للتحسين موضع ترحيب.)

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_Permentment (...). يجب أن تكون نقطة انطلاق جيدة.

Answer 4

هل يمكن أن يكون لديك نظرة على https:/sourceforge.net/projects/swappermulation/ وهو تطبيق جافا لمتطلباتك بالضبط: جهاز كمتقل ينشئ مقايضة. خلقت هذا منذ بعض الوقت محدثة مؤخرا.