N को देखते हुए, 0.5n से कम आकार के सभी क्रमपरिवर्तन उत्पन्न करें

Jan 08 2021

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

उदाहरण के लिए, n=7यह होगा:

15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [1, 3]
 [2, 1]
 [2, 3]
 [3, 1]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

मेरा वर्तमान विचार आकार के सभी क्रमपरिवर्तन से kकम 0.5nऔर उन्हें जोड़कर उत्पन्न करना है:

using Combinatorics

function generate_half_perm(n)
    half_n = floor(Int, n/2)
    result = []
    for l in 1:half_n
            for c in permutations(1:half_n, l)
                    push!(result, c)
            end
    end
    return result
end

Gener_half_perm (7) तब इस पोस्ट का पहला उदाहरण देता है। मुझे लगता है कि इस कोड को वर्तमान में है ऊपर O(2^(n/2).n)किस संयोग उत्पन्न करने के लिए की जरूरत है एक के बिना कोड की जटिलता, है combinations(1:half_n, l)

मैं सोच रहा था कि क्या कोई बेहतर विचार है जो एक तेज कोड को जन्म दे सकता है जो कि मेरा n संभावना 100 से ऊपर होगा।

मेरे पास इस कोड का उपयोग करने का विचार था [जूलिया में क्रमपरिवर्तन की इष्टतम विधि] लेकिन उत्पादन समारोह को पदावनत किया गया है और इसे इस अन्य उत्तर के साथ प्रतिस्थापित किया जाना चाहिए [उपभोग और चैनलों के साथ उत्पादन कैसे करें] और अब जो मेरे लिए जटिल होने लगा है। समझने के लिए!

यदि आपके पास जूलिया कार्यान्वयन के बिना एक बेहतर विचार एल्गोरिदम है, तो मुझे इसे आज़माने में खुशी होगी :)

छोटा संपादन: मुझे एहसास है कि मैं जो चाहता था:

collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))

धन्यवाद @Przemyslaw Szufel के लिए मुझे इसे खोजने के लिए :)

जवाब

3 PrzemyslawSzufel Jan 08 2021 at 19:21

आपके मान के लिए "N का आधा" 3 के बराबर होगा:

using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))

ध्यान दें कि यह गैर-आवंटन है, इसलिए यदि आप देखना चाहते हैं कि परिणाम collectकी आवश्यकता है:

julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [2, 3]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]