خوارزمية لإرجاع جميع مجموعات عناصر k من n
https://stackoverflow.com/questions/127704
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أريد أن أكتب دالة تأخذ مجموعة من الحروف كوسيطة وعدد من تلك الحروف لتحديدها.
لنفترض أنك قدمت مجموعة مكونة من 8 أحرف وتريد تحديد 3 أحرف منها.ثم يجب أن تحصل على:
8! / ((8 - 3)! * 3!) = 56
المصفوفات (أو الكلمات) في المقابل تتكون من 3 أحرف لكل منها.
المحلول
فن برمجة الكمبيوتر المجلد 4:الملزمة 3 يحتوي على الكثير من هذه الأشياء التي قد تناسب وضعك الخاص بشكل أفضل مما أصفه.
رموز رمادية
المشكلة التي ستواجهها هي بالطبع الذاكرة وبسرعة كبيرة، ستواجه مشاكل في 20 عنصرًا في مجموعتك -- 20ج3 = 1140.وإذا كنت تريد التكرار على المجموعة، فمن الأفضل استخدام خوارزمية كود رمادية معدلة حتى لا تحتفظ بها جميعًا في الذاكرة.هذه تولد المجموعة التالية من المجموعة السابقة وتتجنب التكرار.هناك العديد من هذه لاستخدامات مختلفة.هل نريد تعظيم الاختلافات بين المجموعات المتعاقبة؟تقليل؟إلى آخره.
بعض الأوراق الأصلية التي تصف الرموز الرمادية:
وإليك بعض الأوراق الأخرى التي تتناول الموضوع:
- التنفيذ الفعال لخوارزمية إنشاء مجموعة التبادل المتجاورة لـ Eades وHickey وRead (PDF، مع الكود بلغة باسكال)
- مولدات الجمع
- مسح الرموز الرمادية التوافقية (بوستسكريبت)
- خوارزمية للرموز الرمادية
تشيس توادل (خوارزمية)
فيليب جي تشيس، `الخوارزمية 382:مجموعات من M من كائنات N' (1970)
فهرس المجموعات في الترتيب المعجمي (خوارزمية الأبازيم 515)
يمكنك أيضًا الإشارة إلى المجموعة حسب فهرسها (بالترتيب المعجمي).مع إدراك أن الفهرس يجب أن يكون لديه قدر من التغيير من اليمين إلى اليسار بناءً على الفهرس، يمكننا بناء شيء يجب أن يستعيد المجموعة.
لذلك، لدينا مجموعة {1،2،3،4،5،6} ...ونحن نريد ثلاثة عناصر.لنفترض {1,2,3} يمكننا القول أن الفرق بين العناصر واحد ومرتب وأقل ما يمكن.{1،2،4} به تغيير واحد وهو رقم معجمي 2.لذا فإن عدد "التغييرات" في المكان الأخير يمثل تغييرًا واحدًا في الترتيب المعجمي.المكان الثاني، مع تغيير واحد {1،3،4} لديه تغيير واحد ولكنه يمثل المزيد من التغيير لأنه في المركز الثاني (بما يتناسب مع عدد العناصر في المجموعة الأصلية).
الطريقة التي وصفتها هي تفكيكية، كما يبدو، من المجموعة إلى الفهرس، نحتاج إلى القيام بالعكس - وهو أمر أكثر صعوبة.هذه هي الطريقة أبازيم يحل المشكلة.لقد كتبت بعض ج لحسابهم, ، مع تغييرات طفيفة – لقد استخدمت فهرس المجموعات بدلاً من نطاق الأرقام لتمثيل المجموعة، لذلك نحن نعمل دائمًا من 0...n.ملحوظة:
- نظرًا لأن المجموعات غير مرتبة، {1,3,2} = {1,2,3} -- فإننا نرتبها لتكون معجمية.
- تحتوي هذه الطريقة على 0 ضمني لبدء المجموعة للفرق الأول.
فهرس المجموعات في الترتيب المعجمي (مكافري)
هنالك طريق اخر: مفهومه أسهل في الفهم والبرمجة ولكنه بدون تحسينات الأبازيم.ولحسن الحظ، فإنه أيضًا لا ينتج مجموعات مكررة:
مجموعة 
الذي يزيد 
, ، أين 
.
على سبيل المثال: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1).إذن، المجموعة المعجمية السابعة والعشرون المكونة من أربعة أشياء هي:{1،2،5،6}، هذه هي فهارس أي مجموعة تريد إلقاء نظرة عليها.المثال أدناه (OCaml)، يتطلب choose الوظيفة، متروكة للقارئ:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
مكرر مجموعات صغيرة وبسيطة
يتم توفير الخوارزميتين التاليتين للأغراض التعليمية.يقومون بتنفيذ مجموعات مكررة ومجلد (أكثر عمومية).إنهم سريعون قدر الإمكان، ولديهم التعقيد O(نجك).استهلاك الذاكرة لا بد منه k.
سنبدأ بالمكرِّر، الذي سيستدعي الوظيفة التي يوفرها المستخدم لكل مجموعة
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
سوف يستدعي الإصدار الأكثر عمومية الوظيفة التي يوفرها المستخدم مع متغير الحالة، بدءًا من الحالة الأولية.نظرًا لأننا نحتاج إلى تمرير الحالة بين حالات مختلفة، فلن نستخدم حلقة for، بل نستخدم التكرار بدلاً من ذلك،
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
نصائح أخرى
شركة#:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
الاستخدام:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
نتيجة:
123
124
125
134
135
145
234
235
245
345
حل جافا القصير:
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
ستكون النتيجة
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
هل يمكنني تقديم حل بايثون العودي لهذه المشكلة؟
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
مثال على الاستخدام:
>>> len(list(choose_iter("abcdefgh",3)))
56
أنا أحب ذلك لبساطته.
لنفترض أن مجموعة الحروف الخاصة بك تبدو كما يلي:"ABCDEFGH".لديك ثلاثة مؤشرات (i، j، k) تشير إلى الحروف التي ستستخدمها للكلمة الحالية، ابدأ بـ:
A B C D E F G H ^ ^ ^ i j k
أولاً، قم بتغيير k، وبالتالي تبدو الخطوة التالية كما يلي:
A B C D E F G H ^ ^ ^ i j k
إذا وصلت إلى النهاية، فاستمر في تغيير j ثم k مرة أخرى.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
بمجرد وصولك إلى G، تبدأ أيضًا في التغيير i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
مكتوب في الكود هذا يبدو شيء من هذا القبيل
void print_combinations(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
تختار الخوارزمية العودية التالية جميع مجموعات العناصر k من مجموعة مرتبة:
- اختر العنصر الأول
iمن مجموعتك - يجمع
iمع كل مجموعة منk-1العناصر المختارة بشكل متكرر من مجموعة العناصر الأكبر منi.
كرر ما سبق لكل منهما i في المجموعة.
ومن الضروري أن تختار بقية العناصر أكبر من حجمها i, ، لتجنب التكرار.بهذه الطريقة سيتم اختيار [3،5] مرة واحدة فقط، حيث يتم دمج [3] مع [5]، بدلاً من مرتين (الشرط يلغي [5] + [3]).بدون هذا الشرط تحصل على اختلافات بدلاً من المجموعات.
لقد وجدت هذا الموضوع مفيدًا واعتقدت أنني سأضيف حل Javascript يمكنك إدخاله في Firebug.اعتمادًا على محرك JS الخاص بك، قد يستغرق الأمر بعض الوقت إذا كانت سلسلة البداية كبيرة.
function string_recurse(active, rest) {
if (rest.length == 0) {
console.log(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
string_recurse(active, rest.substring(1, rest.length));
}
}
string_recurse("", "abc");
يجب أن يكون الإخراج كما يلي:
abc
ab
ac
a
bc
b
c
في C++، سينتج الروتين التالي جميع مجموعات مسافة الطول (الأول، ك) بين النطاق [الأول، الأخير):
#include <algorithm>
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
يمكن استخدامه مثل هذا:
#include <string>
#include <iostream>
int main()
{
std::string s = "12345";
std::size_t comb_size = 3;
do
{
std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));
return 0;
}
سيؤدي هذا إلى طباعة ما يلي:
123
124
125
134
135
145
234
235
245
345
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
مثال قصير في بايثون:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
وللتوضيح، تم وصف الطريقة العودية بالمثال التالي:
مثال:أ ب ج د ه
جميع المجموعات المكونة من 3 ستكون:
- A مع كل المجموعات المكونة من 2 من الباقي (B C D E)
- B مع كل المجموعات المكونة من 2 من الباقي (C D E)
- C مع كل المجموعات المكونة من 2 من الباقي (D E)
خوارزمية متكررة بسيطة في هاسكل
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
نحدد أولاً الحالة الخاصة، أي.اختيار العناصر الصفريةوتنتج نتيجة واحدة، وهي قائمة فارغة (أي.قائمة تحتوي على قائمة فارغة).
من أجل ن > 0، x يمر عبر كل عنصر من عناصر القائمة و xs هو كل عنصر بعد x.
rest مختارات n - 1 عناصر من xs باستخدام مكالمة متكررة ل combinations.النتيجة النهائية للوظيفة هي قائمة حيث يوجد كل عنصر x : rest (أي.القائمة التي لديها x كرأس و rest كذيل) لكل قيمة مختلفة x و rest.
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
وبالطبع، نظرًا لأن هاسكل كسول، يتم إنشاء القائمة تدريجيًا حسب الحاجة، حتى تتمكن من تقييم المجموعات الكبيرة بشكل كبير بشكل جزئي.
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
وهنا يأتي الجد كوبول، اللغة المسيئة كثيرًا.
لنفترض مصفوفة مكونة من 34 عنصرًا، كل منها 8 بايت (اختيار عشوائي تمامًا). الفكرة هي تعداد جميع المجموعات الممكنة المكونة من 4 عناصر وتحميلها في مصفوفة.
نستخدم 4 مؤشرات، واحد لكل مركز في مجموعة الأربعة
تتم معالجة المصفوفة على النحو التالي:
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
نحن نختلف idx4 من 4 إلى النهاية.لكل idx4 نحصل على مجموعة فريدة من مجموعات من أربع.عندما يصل idx4 إلى نهاية المصفوفة، نقوم بزيادة idx3 بمقدار 1 وتعيين idx4 إلى idx3+1.ثم نقوم بتشغيل idx4 حتى النهاية مرة أخرى.نواصل بهذه الطريقة، ونزيد idx3 وidx2 وidx1 على التوالي حتى يصبح موضع idx1 أقل من 4 من نهاية المصفوفة.هذا ينهي الخوارزمية.
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
التكرارات الأولى:
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
مثال كوبول:
01 DATA_ARAY.
05 FILLER PIC X(8) VALUE "VALUE_01".
05 FILLER PIC X(8) VALUE "VALUE_02".
etc.
01 ARAY_DATA OCCURS 34.
05 ARAY_ITEM PIC X(8).
01 OUTPUT_ARAY OCCURS 50000 PIC X(32).
01 MAX_NUM PIC 99 COMP VALUE 34.
01 INDEXXES COMP.
05 IDX1 PIC 99.
05 IDX2 PIC 99.
05 IDX3 PIC 99.
05 IDX4 PIC 99.
05 OUT_IDX PIC 9(9).
01 WHERE_TO_STOP_SEARCH PIC 99 COMP.
* Stop the search when IDX1 is on the third last array element:
COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3
MOVE 1 TO IDX1
PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
COMPUTE IDX2 = IDX1 + 1
PERFORM UNTIL IDX2 > MAX_NUM
COMPUTE IDX3 = IDX2 + 1
PERFORM UNTIL IDX3 > MAX_NUM
COMPUTE IDX4 = IDX3 + 1
PERFORM UNTIL IDX4 > MAX_NUM
ADD 1 TO OUT_IDX
STRING ARAY_ITEM(IDX1)
ARAY_ITEM(IDX2)
ARAY_ITEM(IDX3)
ARAY_ITEM(IDX4)
INTO OUTPUT_ARAY(OUT_IDX)
ADD 1 TO IDX4
END-PERFORM
ADD 1 TO IDX3
END-PERFORM
ADD 1 TO IDX2
END_PERFORM
ADD 1 TO IDX1
END-PERFORM.
فيما يلي تطبيق أنيق وعام في Scala، كما هو موضح في 99 مشاكل سكالا.
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}
إذا كان بإمكانك استخدام بناء جملة SQL - على سبيل المثال، إذا كنت تستخدم LINQ للوصول إلى حقول بنية أو مصفوفة، أو الوصول مباشرة إلى قاعدة بيانات تحتوي على جدول يسمى "Alphabet" مع حقل حرف واحد فقط "Letter"، فيمكنك التكيف مع ما يلي شفرة:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
سيؤدي هذا إلى إرجاع جميع المجموعات المكونة من 3 أحرف، بغض النظر عن عدد الأحرف الموجودة في جدول "الأبجدية" (يمكن أن تكون 3، 8، 10، 27، وما إلى ذلك).
إذا كان ما تريده هو كل التباديل، وليس المجموعات (أي.تريد أن يتم اعتبار "ACB" و"ABC" مختلفين، بدلاً من الظهور مرة واحدة فقط) ما عليك سوى حذف السطر الأخير (السطر AND) ويتم ذلك.
نشره:بعد إعادة قراءة السؤال، أدركت أن المطلوب هو عام خوارزمية، وليست مجرد خوارزمية محددة لحالة اختيار 3 عناصر.إجابة آدم هيوز هي الإجابة الكاملة، ولسوء الحظ لا أستطيع التصويت عليها (حتى الآن).هذه الإجابة بسيطة ولكنها تعمل فقط عندما تريد 3 عناصر بالضبط.
إصدار آخر من C# مع توليد كسول للمؤشرات المجمعة.يحتفظ هذا الإصدار بمصفوفة واحدة من المؤشرات لتحديد التعيين بين قائمة جميع القيم وقيم المجموعة الحالية، أي.يستخدم باستمرار نعم) مساحة إضافية خلال فترة التشغيل بأكملها.يقوم الكود بإنشاء مجموعات فردية، بما في ذلك المجموعة الأولى، في نعم) وقت.
public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
if (k < 0 || values.Length < k)
yield break; // invalid parameters, no combinations possible
// generate the initial combination indices
var combIndices = new int[k];
for (var i = 0; i < k; i++)
{
combIndices[i] = i;
}
while (true)
{
// return next combination
var combination = new T[k];
for (var i = 0; i < k; i++)
{
combination[i] = values[combIndices[i]];
}
yield return combination;
// find first index to update
var indexToUpdate = k - 1;
while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
{
indexToUpdate--;
}
if (indexToUpdate < 0)
yield break; // done
// update combination indices
for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
{
combIndices[indexToUpdate] = combIndex;
}
}
}
رمز الاختبار:
foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
System.Console.WriteLine(String.Join(" ", combination));
}
انتاج:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
هنا لديك نسخة مُقيَّمة كسولة من تلك الخوارزمية المشفرة بلغة C#:
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
وجزء الاختبار:
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
نأمل أن يكون هذا مساعدتك!
كان لدي خوارزمية التقليب التي استخدمتها لمشروع أويلر، في بيثون:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
لو
n<len(l)
يجب أن يكون لديك كل التركيبة التي تحتاجها دون تكرار، هل تحتاجها؟
إنه مولد، لذا يمكنك استخدامه في شيء مثل هذا:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
https://Gist.github.com/3118596
هناك تطبيق لجافا سكريبت.لديها وظائف للحصول على مجموعات k وجميع مجموعات مصفوفة من أي كائنات.أمثلة:
k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]
combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
نسخة كلوجر:
(defn comb [k l]
(if (= 1 k) (map vector l)
(apply concat
(map-indexed
#(map (fn [x] (conj x %2))
(comb (dec k) (drop (inc %1) l)))
l))))
لنفترض أن مجموعة الحروف الخاصة بك تبدو كما يلي:"ABCDEFGH".لديك ثلاثة مؤشرات (i، j، k) تشير إلى الحروف التي ستستخدمها للكلمة الحالية، ابدأ بـ:
A B C D E F G H ^ ^ ^ i j k
أولاً، قم بتغيير k، وبالتالي تبدو الخطوة التالية كما يلي:
A B C D E F G H ^ ^ ^ i j k
إذا وصلت إلى النهاية، فاستمر في تغيير j ثم k مرة أخرى.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
بمجرد وصولك إلى G، تبدأ أيضًا في التغيير i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
function initializePointers($cnt) {
$pointers = [];
for($i=0; $i<$cnt; $i++) {
$pointers[] = $i;
}
return $pointers;
}
function incrementPointers(&$pointers, &$arrLength) {
for($i=0; $i<count($pointers); $i++) {
$currentPointerIndex = count($pointers) - $i - 1;
$currentPointer = $pointers[$currentPointerIndex];
if($currentPointer < $arrLength - $i - 1) {
++$pointers[$currentPointerIndex];
for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
}
return true;
}
}
return false;
}
function getDataByPointers(&$arr, &$pointers) {
$data = [];
for($i=0; $i<count($pointers); $i++) {
$data[] = $arr[$pointers[$i]];
}
return $data;
}
function getCombinations($arr, $cnt)
{
$len = count($arr);
$result = [];
$pointers = initializePointers($cnt);
do {
$result[] = getDataByPointers($arr, $pointers);
} while(incrementPointers($pointers, count($arr)));
return $result;
}
$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);
مرتكز على https://stackoverflow.com/a/127898/2628125, ، ولكن أكثر تجريدًا، لأي حجم من المؤشرات.
لقد قمت بإنشاء حل في SQL Server 2005 لهذا الغرض، ونشرته على موقع الويب الخاص بي: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
فيما يلي مثال لإظهار الاستخدام:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
نتائج:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
هذا هو اقتراحي في C++
لقد حاولت أن أفرض أقل قدر ممكن من القيود على نوع المكرر حتى يتمكن هذا الحل من افتراض مكرر للأمام فقط، ويمكن أن يكون مُنشئًا.يجب أن يعمل هذا مع أي حاوية قياسية.في الحالات التي لا تكون فيها الوسيطات منطقية، يتم طرح std::invalid_argumnent
#include <vector>
#include <stdexcept>
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
كل ما قيل وفعل هنا يأتي رمز O'caml لذلك.الخوارزمية واضحة من الكود ..
let combi n lst =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
[] -> []
| (h::t) -> (combi t (h::c))@(combi t c)
in
combi lst []
;;
إليك التعليمات البرمجية التي كتبتها مؤخرًا في Java، والتي تحسب وتعيد جميع مجموعات العناصر "num" من العناصر "outOf".
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
حل جافا سكريبت موجز:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
فيما يلي طريقة تمنحك جميع المجموعات ذات الحجم المحدد من سلسلة ذات طول عشوائي.يشبه حل quinmars، ولكنه يعمل مع مدخلات و k متنوعة.
يمكن تغيير الكود ليلتف حوله، أي 'dab' من الإدخال 'abcd' w k=3.
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
إخراج "abcde":
ABC عبد ابي ACD الآس ادي BCD قبل الميلاد BDE CDE
لقد قمت بكتابة فصل دراسي للتعامل مع الوظائف الشائعة للعمل مع معامل ذي الحدين، وهو نوع المشكلة التي تندرج تحتها مشكلتك.ويقوم بالمهام التالية:
يقوم بإخراج جميع فهارس K بتنسيق لطيف لأي ملف N اختر K.يمكن استبدال فهارس K بسلاسل أو أحرف وصفية أكثر.هذه الطريقة تجعل حل هذا النوع من المشاكل أمرًا تافهًا للغاية.
تحويل فهارس K إلى الفهرس المناسب للإدخال في جدول المعاملات ذات الحدين الذي تم فرزه.هذه التقنية أسرع بكثير من التقنيات المنشورة القديمة التي تعتمد على التكرار.ويتم ذلك باستخدام خاصية رياضية متأصلة في مثلث باسكال.ورقتي تتحدث عن هذاأعتقد أنني أول من اكتشف هذه التقنية ونشرها، لكن قد أكون مخطئًا.
لتحويل الفهرس الموجود في جدول معاملات ذات الحدين المصنف إلى فهارس K المقابلة.
الاستخدامات مارك دومينوس طريقة لحساب معامل ذات الحدين، وهو أقل احتمالا للتجاوز ويعمل مع أعداد أكبر.
تتم كتابة الفصل في .NET C# ويوفر طريقة لإدارة الكائنات المرتبطة بالمشكلة (إن وجدت) باستخدام قائمة عامة.يأخذ منشئ هذه الفئة قيمة منطقية تسمى InitTable والتي عندما تكون صحيحة ستنشئ قائمة عامة للاحتفاظ بالكائنات المراد إدارتها.إذا كانت هذه القيمة خاطئة، فلن يتم إنشاء الجدول.لا يلزم إنشاء الجدول لتنفيذ الطرق الأربع المذكورة أعلاه.يتم توفير أساليب الوصول للوصول إلى الجدول.
توجد فئة اختبار مرتبطة توضح كيفية استخدام الفئة وطرقها.لقد تم اختباره على نطاق واسع مع حالتين ولا توجد أخطاء معروفة.
لقراءة المزيد عن هذا الفصل وتنزيل الكود، راجع جدولة معامل ذات الحدين.
لا ينبغي أن يكون من الصعب تحويل هذه الفئة إلى C++.
الخوارزمية:
- عد من 1 إلى 2^ن.
- تحويل كل رقم إلى تمثيله الثنائي.
- قم بترجمة كل بتة إلى عناصر من مجموعتك، بناءً على الموضع.
شركة#:
void Main()
{
var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
var kElement = 2;
for(var i = 1; i < Math.Pow(2, set.Length); i++) {
var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
var cnt = Regex.Matches(Regex.Escape(result), "1").Count;
if (cnt == kElement) {
for(int j = 0; j < set.Length; j++)
if ( Char.GetNumericValue(result[j]) == 1)
Console.Write(set[j]);
Console.WriteLine();
}
}
}
لماذا يعمل؟
هناك اعتراض بين المجموعات الفرعية لمجموعة n-element وتسلسل n-bit.
وهذا يعني أنه يمكننا معرفة عدد المجموعات الفرعية الموجودة عن طريق حساب التسلسلات.
على سبيل المثال، يمكن تمثيل مجموعة العناصر الأربعة أدناه بتسلسلات مختلفة {0,1} X {0, 1} X {0, 1} X {0, 1} (أو 2^4).
لذا - كل ما علينا فعله هو العد من 1 إلى 2^n للعثور على جميع المجموعات. (نتجاهل المجموعة الفارغة.) بعد ذلك، قم بترجمة الأرقام إلى تمثيلها الثنائي.ثم استبدل عناصر مجموعتك بالبتات "on".
إذا كنت تريد الحصول على نتائج عنصر k فقط، فلا تطبع إلا عندما تكون وحدات k بت قيد التشغيل.
(إذا كنت تريد جميع المجموعات الفرعية بدلاً من المجموعات الفرعية ذات الطول k، فقم بإزالة الجزء cnt/kElement.)
(للحصول على إثبات، راجع برنامج MIT التعليمي المجاني الرياضيات لعلوم الكمبيوتر، Lehman et al، القسم 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )
القفز على العربة ونشر حل آخر.هذا تطبيق Java عام.مدخل: (int k) هو عدد العناصر للاختيار و (List<T> list) هي القائمة للاختيار من بينها.إرجاع قائمة المجموعات (List<List<T>>).
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
