ما هي الخوارزمية التي يمكن أن تحسب مجموعة الطاقة من مجموعة معينة؟
سؤال
أرغب في إنشاء قائمة فريدة من مجموعات الأرقام بناءً على قائمة بداية بالأرقام.
مثال ابدأ 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
المحلول
هناك اسم لما تطلبه. يطلق عليه مجموعة الطاقة.
قادني 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)
الزائفة
- هل تم تمرير المجموعة فارغة؟ تم (لاحظ أن مجموعة القوة من {} هي {{}})
- إذا لم يكن كذلك ، خذ عنصرًا
- طريقة الاتصال بشكل متكرر في بقية المجموعة
- إرجاع المجموعة المكونة من اتحاد
- قوى المجموعة بدون العنصر (من المكالمة العودية)
- هذه المجموعة نفسها (أي ، 2.1) ولكن مع كل عنصر من العناصر في الاتحاد مع العنصر الذي تم إخراجه في البداية
نصائح أخرى
فقط العد 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}
def power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
مثل إجابة 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 بشكل جيد في روبي.
من تعليق من قبل OP (نسخ تحرير):
المثال هو شكل مبسط لما أفعله بالفعل. الأرقام هي كائنات لها خاصية "Qty" ، وأريد تلخيص الكميات لكل مجموعة ممكنة ثم اخترت المجموعة التي تستخدم معظم الكائنات حيث مجموع الكميات
N
هو ضمن بعض الحدود الأخرى ، على سبيل المثالx < N < y
.
ما لديك هو مشكلة التحسين. ما افترضته هو أن الطريقة الصحيحة للتعامل مع مشكلة التحسين هذه هي تحللها إلى مشكلة التعداد (وهو ما طلبته) ثم مشكلة ترشيح (التي من المفترض أنك تعرف كيفية القيام بها).
ما لا تدركه بعد هو أن هذا النوع من الحلول يعمل فقط (أ) للتحليل النظري ، أو (ب) لقيم صغيرة جدًا من n
. التعداد الذي تطلبه هو الأسي في n
, ، مما يعني أنك ستنتهي بشيء قد يستغرق وقتًا طويلاً حتى لا يركض في الممارسة العملية.
لذلك ، اكتشف كيفية طرح مشكلة التحسين الخاصة بك على هذا النحو ، اكتب سؤالًا جديدًا ، وقم بتحرير هذا السؤال للإشارة إليه.
الحلول العودية والتكرارية لحساب الطاقة المحددة في المخطط. لم يتم اختباره بالكامل رغم ذلك
(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)))))
فيما يلي حل عودية ، يشبه تلك المنشورة بالفعل. بعض التأكيدات توفر كنوع من اختبارات الوحدة. لم أتمكن من استخدام "مجموعة" نوع بيثون لتمثيل مجموعة من المجموعات. قال بيثون أن "مجموعة الكائنات غير قابلة للتطبيق" عند محاولة التعبير مثل "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)