ما هي الخوارزمية التي يمكن أن تحسب مجموعة الطاقة من مجموعة معينة؟

Question

أرغب في إنشاء قائمة فريدة من مجموعات الأرقام بناءً على قائمة بداية بالأرقام.

مثال ابدأ list = [1,2,3,4,5] لكن يجب أن تعمل الخوارزمية [1,2,3...n]

result = 

[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]

ملحوظة. لا أريد مجموعات مكررة ، على الرغم من أنني أستطيع العيش معهم ، على سبيل المثال ، في المثال أعلاه ، لا أحتاج حقًا إلى المزيج [1،3،2] لأنه موجود بالفعل مثل [1،2،3

Answer 1

هناك اسم لما تطلبه. يطلق عليه مجموعة الطاقة.

قادني Googling لـ "خوارزمية مجموعة القوة" إلى هذا الحل العودية.

خوارزمية روبي

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)  
   subset | subset.map { |x| x | [p] }
end

الحدس مجموعة القوة

إذا s = (a ، b ، c) ثم مجموعة الطاقة(S) هي مجموعة جميع المجموعات الفرعيةمجموعة الطاقة(s) = {() ، (a) ، (b) ، (c) ، (a ، b) ، (a ، c) ، (b ، c) ، (a ، b ، c)}}

أول "خدعة" هي محاولة ذلك حدد متكرر.

ماذا ستكون حالة توقف؟

s = () لديه ماذا مجموعة الطاقة(س)؟

كيف احصل على لذلك؟

قلل من عنصر واحد

فكر في إخراج عنصر - في المثال أعلاه ، أخرج {c}

s = (أ ، ب) ثم مجموعة الطاقة(s) = {() ، (a) ، (b) ، (a ، b)}

ما المفقود؟

مجموعة الطاقة(s) = {(c) ، (a ، c) ، (b ، c) ، (a ، b ، c)}

أمم

لاحظ أي أوجه تشابه؟ انظر مرة أخرى ...

مجموعة الطاقة(s) = {() ، (a) ، (b) ، (c) ، (a ، b) ، (a ، c) ، (b ، c) ، (a ، b ، c)}}

أخرج أي عنصر

مجموعة الطاقة(s) = {() ، (a) ، (b) ، (c) ، (a ، b) ، (a ، c) ، (b ، c) ، (a ، b ، c)}} هو

مجموعة الطاقة(s - {c}) = {() ، (a) ، (b) ، (a ، b)}

{c} u مجموعة الطاقة(s - {c}) = {(c) ، (a ، c) ، (b ، c) ، (a ، b ، c)}

مجموعة الطاقة(S) = مجموعة الطاقة(S - {e_أنا}) u ({e_أنا} u مجموعة الطاقة(S - {e_أنا}))

حيث ه_أنا هو عنصر S (Singleton)

الزائفة

1. هل تم تمرير المجموعة فارغة؟ تم (لاحظ أن مجموعة القوة من {} هي {{}})
2. إذا لم يكن كذلك ، خذ عنصرًا
   • طريقة الاتصال بشكل متكرر في بقية المجموعة
   • إرجاع المجموعة المكونة من اتحاد
     1. قوى المجموعة بدون العنصر (من المكالمة العودية)
     2. هذه المجموعة نفسها (أي ، 2.1) ولكن مع كل عنصر من العناصر في الاتحاد مع العنصر الذي تم إخراجه في البداية

Answer 2

فقط العد 0 إلى 2^n - 1 وطباعة الأرقام وفقًا للتمثيل الثنائي لعددك. أ 1 يعني أنك تطبع هذا الرقم و 0 يعني أنك لا تفعل ذلك. مثال:

set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
        00011 => print {1, 2}
        00100 => print {3}
        00101 => print {1, 3}
        00110 => print {2, 3}
        00111 => print {1, 2, 3}
        ...
        11111 => print {1, 2, 3, 4, 5}

Answer 3

def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end

Answer 4

مثل إجابة Hobodave ، ولكن التكرار وأسرع (في روبي). كما أنه يعمل مع كليهما Array و Set.

def Powerset(set)
    ret = set.class[set.class[]]
    set.each do |s|
        deepcopy = ret.map { |x| set.class.new(x) }
        deepcopy.map { |r| r << s }
        ret = ret + deepcopy
    end
    return ret
end

في اختباراتي ، لا تعمل طريقة Ivlad بشكل جيد في روبي.

Answer 5

من تعليق من قبل OP (نسخ تحرير):

المثال هو شكل مبسط لما أفعله بالفعل. الأرقام هي كائنات لها خاصية "Qty" ، وأريد تلخيص الكميات لكل مجموعة ممكنة ثم اخترت المجموعة التي تستخدم معظم الكائنات حيث مجموع الكميات N هو ضمن بعض الحدود الأخرى ، على سبيل المثال x < N < y.

ما لديك هو مشكلة التحسين. ما افترضته هو أن الطريقة الصحيحة للتعامل مع مشكلة التحسين هذه هي تحللها إلى مشكلة التعداد (وهو ما طلبته) ثم مشكلة ترشيح (التي من المفترض أنك تعرف كيفية القيام بها).

ما لا تدركه بعد هو أن هذا النوع من الحلول يعمل فقط (أ) للتحليل النظري ، أو (ب) لقيم صغيرة جدًا من n. التعداد الذي تطلبه هو الأسي في n, ، مما يعني أنك ستنتهي بشيء قد يستغرق وقتًا طويلاً حتى لا يركض في الممارسة العملية.

لذلك ، اكتشف كيفية طرح مشكلة التحسين الخاصة بك على هذا النحو ، اكتب سؤالًا جديدًا ، وقم بتحرير هذا السؤال للإشارة إليه.

Answer 6

الحلول العودية والتكرارية لحساب الطاقة المحددة في المخطط. لم يتم اختباره بالكامل رغم ذلك

(define (power_set set)
      (cond 
        ((empty? set) (list '()))
        (else
         (let ((part_res (power_set (cdr set))))
           (append (map (lambda (s) (cons (car set) s)) part_res) part_res)))))

(define (power_set_iter set)
  (let loop ((res '(())) (s set))
    (if (empty? s)
        res
        (loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))

Answer 7

فيما يلي حل عودية ، يشبه تلك المنشورة بالفعل. بعض التأكيدات توفر كنوع من اختبارات الوحدة. لم أتمكن من استخدام "مجموعة" نوع بيثون لتمثيل مجموعة من المجموعات. قال بيثون أن "مجموعة الكائنات غير قابلة للتطبيق" عند محاولة التعبير مثل "S.Add (set ())".

انظر أيضًا الحلول في العديد من لغات البرمجة في http://rosettacode.org/wiki/power_set

def generatePowerSet(s, niceSorting = True):
    """Generate power set of a given set.

    The given set, as well as, return set of sets, are implemented
    as lists.

    "niceSorting" optionnaly sorts the powerset by increasing subset size.
    """
    import copy

    def setCmp(a,b):
        """Compare two sets (implemented as lists) for nice sorting"""
        if len(a) < len(b):
            return -1
        elif len(a) > len(b):
            return 1
        else:
            if len(a) == 0:
                return 0
            else:
                if a < b:
                    return -1
                elif a > b:
                    return 1
                else:
                    return 0

    # Initialize the power set "ps" of set "s" as an empty set                    
    ps = list()

    if len(s) == 0:
        ps.append(list())
    else:

        # Generate "psx": the power set of "sx", 
        # which is "s" without a chosen element "x"
        sx = copy.copy(s)
        x = sx.pop()
        psx = generatePowerSet(sx, False)        

        # Include "psx" to "ps"      
        ps.extend(psx)

        # Include to "ps" any set, which contains "x"
        # Such included sets are obtained by adding "x" to any subset of "sx"
        for y in psx:
            yx = copy.copy(y)
            yx.append(x)
            ps.append(yx)

    if niceSorting:
        ps.sort(cmp=setCmp)      

    return ps

assert generatePowerSet([]) == [[]]

assert generatePowerSet(['a']) == [[], ['a']]

assert generatePowerSet(['a', 'b']) == [[], ['a'], ['b'], ['a', 'b']]

assert generatePowerSet(['a', 'b','c']) == [[], 
                                            ['a'], ['b'], ['c'], 
                                            ['a', 'b'], ['a', 'c'], ['b', 'c'],
                                            ['a', 'b', 'c'] ]

assert generatePowerSet(['a', 'b','c'], False) == [ [], 
                                                    ['a'], 
                                                    ['b'], 
                                                    ['a', 'b'], 
                                                    ['c'], 
                                                    ['a', 'c'], 
                                                    ['b', 'c'], 
                                                    ['a', 'b', 'c'] ]

print generatePowerSet(range(4), True)