सभी क्रमपरिवर्तनों के माध्यम से एक समय में एक स्वैप

Question

एन विशिष्ट वस्तुओं की एक सूची को देखते हुए, मैं एक समय में केवल एक जोड़ी मूल्यों को स्वैप करने वाले आइटमों के प्रत्येक क्रमपरिवर्तन के माध्यम से कैसे कदम उठा सकता हूं? (मुझे लगता है कि यह संभव है, यह निश्चित रूप से ऐसा होना चाहिए जैसा कि यह होना चाहिए।)

जो मैं खोज रहा हूं वह एक पुनरावर्तक है जो स्वैप करने के लिए वस्तुओं की अगली जोड़ी के सूचकांक उत्पन्न करता है, जैसे कि अगर पुनरावृत्त एन! -1 बार यह एन के माध्यम से कदम होगा! कुछ क्रम में सूची के क्रमपरिवर्तन। यदि इसे एक बार फिर से चालू करना सूची को अपने प्रारंभिक क्रम में पुनर्स्थापित करेगा जो बोनस होगा, लेकिन यह एक आवश्यकता नहीं है। यदि सभी जोड़ों में पहली (resp। अंतिम) तत्व शामिल होता है जो कि एक जोड़ी में से एक है, ताकि फ़ंक्शन को केवल एक मान वापस करने की आवश्यकता हो, जो कि बोनस भी होगा।

उदाहरण: - 3 तत्वों के लिए, आप अंतिम तत्व को क्रमशः पहले और दूसरे तत्वों के साथ क्रमशः लूप के माध्यम से लूप करने के लिए स्वैप कर सकते हैं, जैसे: (एबीसी) स्वैप 0-2 => (सीबीए) 1-2 (कैब) 0-2 (बीएसी) 1-2 (बीसीए) 0-2 (एसीबी)।

मैं सी में कार्यान्वित कर रहा हूं, लेकिन शायद अधिकांश भाषाओं में समाधान निकाल सकता हूं।

Answer 1

आह, एक बार मैंने एन = 4 के लिए अनुक्रम की गणना की ("हमेशा किसी अन्य वस्तु के साथ पहली वस्तु को स्वैप करें" के साथ, मैं ओईआईएस में अनुक्रम A123400 ढूंढने में सक्षम था, जिसने मुझे बताया कि मुझे "एहरलिच की स्वैप विधि" "।

Google ने मुझे a C++ implementation पाया, जो मुझे लगता है कि this जीपीएल के तहत है। मुझे Knuth's fascicle 2b भी मिला है जो मेरी समस्या के लिए विभिन्न समाधानों का वर्णन करता है।

एक बार जब मैंने परीक्षण सी कार्यान्वयन किया है तो मैं इसे कोड के साथ अपडेट कर दूंगा।

यहां कुछ perl कोड है जो Knuth के वर्णन के आधार पर एहरलिच की विधि लागू करता है। 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

सी ++ मानक लाइब्रेरी फ़ंक्शन next_permuation (...) पर एक नज़र डालें। यह एक अच्छा प्रारंभिक बिंदु होना चाहिए।

Answer 3

मुझे यकीन है कि यह आप के लिए देर से भी है, लेकिन मैं इस सवाल का एक अच्छा इसके अतिरिक्त मिला: Steinhaus–Johnson–Trotter algorithm और उसके संस्करण वास्तव में करना आपने जो पूछा इसके अलावा इसमें अतिरिक्त संपत्ति है जो यह हमेशा आसन्न सूचकांक को स्वैप करती है। मैं एक iterator के रूप में वेरिएंट (यहां तक ​​कि के) जावा में से एक को लागू करने की कोशिश की और अच्छी तरह से काम करता है:

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(); 
    } 
} 

यह एक अनंत इटरेटर कि अंत में चक्र के पुनः प्रारंभ करने के लिए इसे संशोधित करने के लिए आसान हो सकता है या एक था इटेटरेटर जो अगली क्रमपरिवर्तन के बजाय स्वैप किए गए इंडेक्स को वापस कर देगा।

Here विभिन्न कार्यान्वयन एकत्र करने वाला एक और लिंक।

Answer 4

आप https://sourceforge.net/projects/swappermutation/ पर एक नज़र डाल सकते हैं जो वास्तव में आपकी आवश्यकताओं के जावा कार्यान्वयन है: एक इटरेटर जो स्वैप उत्पन्न करता है। इसे हाल ही में अपडेट किया गया कुछ समय पहले बनाया गया था।