डुप्लीकेट

Question

उत्पन्न किए बिना स्ट्रिंग के सभी अद्वितीय क्रमिकताओं को ढूंढना स्ट्रिंग के सभी क्रमपरिवर्तनों को ढूंढना एक प्रसिद्ध स्टीनहॉस-जॉनसन-ट्रॉटर एल्गोरिदम द्वारा है। लेकिन अगर स्ट्रिंग ऐसे
AABB के रूप में वर्ण दोहराए गए हैं,
तो संभव अद्वितीय संयोजन 4 हो जाएगा!/(2! * 2!) = 6

इस को प्राप्त करने का एक तरीका यह है कि हम यह स्टोर कर सकते हैं है एक सरणी में या तो और डुप्लीकेट हटा दें।

क्या जॉनसन एल्गोरिदम को संशोधित करने का कोई आसान तरीका है, ताकि हम डुप्लिकेट किए गए क्रमपरिवर्तन उत्पन्न न करें। (सबसे कुशल तरीके से)

Answer 1

मेरे समाधान में, मैं विकल्पों को दोबारा उत्पन्न करता हूं, हर बार उस पत्र को जोड़ने का प्रयास करता हूं जिसे मैंने अभी तक उपयोग नहीं किया है।

#include <string.h> 

void fill(char ***adr,int *pos,char *pref) { 
    int i,z=1; 
    //loop on the chars, and check if should use them 
    for (i=0;i<256;i++) 
     if (pos[i]) { 
      int l=strlen(pref); 
      //add the char 
      pref[l]=i; 
      pos[i]--; 
      //call the recursion 
      fill(adr,pos,pref); 
      //delete the char 
      pref[l]=0; 
      pos[i]++; 
      z=0; 
     } 
    if (z) strcpy(*(*adr)++,pref); 
} 

void calc(char **arr,const char *str) { 
    int p[256]={0}; 
    int l=strlen(str); 
    char temp[l+1]; 
    for (;l>=0;l--) temp[l]=0; 
    while (*str) p[*str++]++; 
    fill(&arr,p,temp); 
} 

उपयोग उदाहरण:

#include <stdio.h> 
#include <string.h> 

int main() { 
    char s[]="AABAF"; 
    char *arr[20]; 
    int i; 
    for (i=0;i<20;i++) arr[i]=malloc(sizeof(s)); 
    calc(arr,s); 
    for (i=0;i<20;i++) printf("%d: %s\n",i,arr[i]); 
    return 0; 
} 

Answer 2

उपयोग निम्नलिखित पुनरावर्ती एल्गोरिदम:

PermutList Permute(SymArray fullSymArray){ 
    PermutList resultList=empty; 
    for(each symbol A in fullSymArray, but repeated ones take only once) { 
     PermutList lesserPermutList= Permute(fullSymArray without A) 
     for (each SymArray item in lesserPermutList){ 
      resultList.add("A"+item); 
     } 
    } 
    return resultList; 
} 

जैसा कि आप देख, यह बहुत आसान है

Answer 3

मुझे लगता है कि इस समस्या को अनिवार्य रूप से समस्या है मल्टीसेट क्रमपरिवर्तन उत्पन्न करने के लिए। यह पेपर प्रासंगिक प्रतीत होता है: जे एफ कोरश पी एस एस फोफलेट। मल्टीसेट क्रमपरिवर्तन के लूपलेस सरणी पीढ़ी । कंप्यूटर जर्नल, 47 (5): 612-621, 2004.

सार से: यह पत्र एक मल्टीसेट के सभी क्रमपरिवर्तन उत्पन्न करने के लिए एक लूपलेस एल्गोरिदम प्रस्तुत करता है। प्रत्येक को एक पूर्ववर्ती बनाकर अपने पूर्ववर्ती से प्राप्त किया जाता है। यह क्रमिक क्रम के लिए सरणी का उपयोग करके पिछले एल्गोरिदम से भिन्न है, लेकिन इसकी लंबाई में केवल भंडारण की आवश्यकता होती है।

Answer 4

पहले स्ट्रिंग को अद्वितीय वर्णों और घटना संख्याओं के सेट में कनवर्ट करें। बनाना -> (3, ए), (1, बी), (2, एन)। (यह स्ट्रिंग और ग्रुपिंग अक्षरों को सॉर्ट करके किया जा सकता है)। फिर, सेट में प्रत्येक पत्र के लिए, उस पत्र को एक पत्र के एक कम से कम सेट के सभी क्रमिक क्रम में प्रस्तुत करें (रिकर्सन नोट करें)। "बनाना" उदाहरण जारी रखते हुए, हमारे पास है: क्रमपरिवर्तन ((3, ए), (1, बी), (2, एन)) = ए: (क्रमपरिवर्तन ((2, ए), (1, बी), (2 , एन)) ++ बी: (क्रमपरिवर्तन ((3, ए), (2, एन)) ++ एन: (क्रमपरिवर्तन ((3, ए), (1, बी), (1, एन))

यहाँ हास्केल में एक काम कर दिया गया है:

circularPermutations::[a]->[[a]] 
circularPermutations xs = helper [] xs [] 
          where helper acc [] _ = acc 
           helper acc (x:xs) ys = 
            helper (((x:xs) ++ ys):acc) xs (ys ++ [x]) 

nrPermutations::[(Int, a)]->[[a]] 
nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))] 
nrPermutations xs = concat (map helper (circularPermutations xs)) 
    where helper ((1,x):xs) = map ((:) x)(nrPermutations xs) 
     helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs)) 

Answer 5

यह एक मुश्किल सवाल है और हम प्रत्यावर्तन उपयोग करने के लिए एक स्ट्रिंग के सभी क्रमपरिवर्तन खोजने की जरूरत है, उदाहरण के लिए "AAB" क्रमपरिवर्तन "AAB" हो जाएगा, " एबीए "और" बीएए " हमें सेट करने की आवश्यकता है ताकि यह सुनिश्चित किया जा सके कि कोई डुप्लिकेट मान नहीं है।

import java.io.*; 
import java.util.HashSet; 
import java.util.*; 
class Permutation { 

    static HashSet<String> set = new HashSet<String>(); 
    public static void main (String[] args) { 
    Scanner in = new Scanner(System.in); 
     System.out.println("Enter :"); 
     StringBuilder str = new StringBuilder(in.nextLine()); 
     NONDuplicatePermutation("",str.toString()); //WITHOUT DUPLICATE PERMUTATION OF STRING 
     System.out.println(set); 
    } 


    public static void NONDuplicatePermutation(String prefix,String str){ 
     //It is nlogn 
     if(str.length()==0){ 
      set.add(prefix); 
     }else{ 
      for(int i=0;i<str.length();i++){ 

       NONDuplicatePermutation(prefix+ str.charAt(i), str.substring(0,i)+str.substring(i+1)); 
      } 
     } 

    } 

}