यह दृष्टिकोण यह एक इटरेटर कि बल्कि permn
की तरह एक समारोह जो सामने पूरी सूची उत्पन्न करता है (एक महंगी आपरेशन) का उपयोग करने से क्रमपरिवर्तन की सूची उत्पादन कर सकता है निर्माण करने के लिए सबसे अच्छा तरीका होगा की तरह लगता है।
ऐसी वस्तुओं के निर्माण पर मार्गदर्शन देखने के लिए एक उत्कृष्ट जगह पाइथन मानक पुस्तकालय में itertools मॉड्यूल है। Itertools आंशिक रूप से आर के लिए a package of the same name के रूप में फिर से कार्यान्वित किया गया है।
require(itertools)
permutations <- function(iterable) {
# Returns permutations of iterable. Based on code given in the documentation
# of the `permutation` function in the Python itertools module:
# http://docs.python.org/library/itertools.html#itertools.permutations
n <- length(iterable)
indicies <- seq(n)
cycles <- rev(indicies)
stop_iteration <- FALSE
nextEl <- function(){
if (stop_iteration){ stop('StopIteration', call. = FALSE) }
if (cycles[1] == 1){ stop_iteration <<- TRUE } # Triggered on last iteration
for (i in rev(seq(n))) {
cycles[i] <<- cycles[i] - 1
if (cycles[i] == 0){
if (i < n){
indicies[i:n] <<- c(indicies[(i+1):n], indicies[i])
}
cycles[i] <<- n - i + 1
}else{
j <- cycles[i]
indicies[c(i, n-j+1)] <<- c(indicies[n-j+1], indicies[i])
return(iterable[indicies])
}
}
}
# chain is used to return a copy of the original sequence
# before returning permutations.
return(chain(list(iterable), new_iterator(nextElem = nextEl)))
}
Knuth गलत उद्धरण के लिए::
निम्नलिखित एक उदाहरण आर के itertools का उपयोग करता है पायथन जनरेटर कि क्रमपरिवर्तन के लिए iterators बनाता है की एक बंदरगाह को लागू करने की है "उपरोक्त कोड में कीड़े से सावधान रहें; मैंने केवल कोशिश की है, यह सही साबित नहीं हुआ है।"
अनुक्रम 1:10
के पहले 3 क्रमपरिवर्तन के लिए, permn
कंप्यूटिंग अनावश्यक क्रमपरिवर्तन के लिए एक भारी कीमत का भुगतान करती है:
> system.time(first_three <- permn(1:10)[1:3])
user system elapsed
134.809 0.439 135.251
> first_three
[[1]]
[1] 1 2 3 4 5 6 7 8 9 10
[[2]]
[1] 1 2 3 4 5 6 7 8 10 9
[[3]]
[1] 1 2 3 4 5 6 7 10 8 9)
हालांकि, इटरेटर permutations
द्वारा लौटाए केवल पहले तीन के लिए क्वेरी की जा सकती है तत्व जो बहुत सारी गणनाओं को बचाते हैं:
> system.time(first_three <- as.list(ilimit(permutations(1:10), 3)))
user system elapsed
0.002 0.000 0.002
> first_three
[[1]]
[1] 1 2 3 4 5 6 7 8 9 10
[[2]]
[1] 1 2 3 4 5 6 7 8 10 9
[[3]]
[1] 1 2 3 4 5 6 7 9 8 10
पायथन एल्गोरिदम permuta उत्पन्न करता है permn
से अलग क्रम में टियां।
सभी क्रमपरिवर्तन कम्प्यूटिंग अभी भी संभव है:
> system.time(all_perms <- as.list(permutations(1:10)))
user system elapsed
498.601 0.672 499.284
अधिक महंगी हालांकि अजगर एल्गोरिथ्म बनाता है के रूप में permn
की तुलना में छोरों का भारी इस्तेमाल। पायथन वास्तव में सी में इस एल्गोरिदम लागू करता है जो व्याख्याित लूप की अक्षमता की भरपाई करता है।
कोड in a gist on GitHub उपलब्ध है। अगर किसी के पास एक बेहतर विचार है, तो दूर चले जाओ!
क्या मुझे कुछ याद आ रही है? क्यों नहीं क्रमपरिवर्तन (एन) [1: एन,]? – Stompchicken
क्रमपरिवर्तन (100,5) [1:10,] कुछ समय लगेगा ... मुझे लगता है कि समस्या है। – Spacedman
आपको शायद 'पहले' से क्या मतलब है इसकी कुछ परिभाषा होनी चाहिए। – John