ما هي الخوارزمية الجيدة وغير العودية لحساب المنتج الديكارتي؟

Question

ملحوظة

هذا ليس سؤالًا خاصًا بـ REBOL.يمكنك الإجابة عليه بأي لغة.

خلفية

ال ريبول تدعم اللغة إنشاء لغات خاصة بالمجال تُعرف باسم "اللهجات" في REBOL لغة.لقد قمت بإنشاء مثل هذه اللهجة لفهم القائمة، وهي غير مدعومة أصلاً في REBOL.

هناك حاجة إلى خوارزمية المنتج الديكارتي الجيدة لفهم القائمة.

المشكلة

لقد استخدمت البرمجة الوصفية لحل هذه المشكلة، وذلك عن طريق إنشاء سلسلة من العمليات المتداخلة ديناميكيًا ثم تنفيذها foreach صياغات.إنه يعمل بشكل جميل.ومع ذلك، نظرًا لأنه ديناميكي، فإن الكود غير قابل للقراءة بشكل كبير.REBOL لا يقوم بالتكرار بشكل جيد.ينفد مساحة المكدس بسرعة ويتعطل.لذا فإن الحل العودي غير وارد.

باختصار، أريد استبدال برمجتي التعريفية بخوارزمية "مضمّنة" قابلة للقراءة وغير متكررة، إن أمكن.يمكن أن يكون الحل بأي لغة، طالما أستطيع إعادة إنتاجه في REBOL.(أستطيع أن أقرأ عن أي لغة برمجة:C#، C، C++، Perl، Oz، Haskell، Erlang، أيًا كان.)

يجب أن أؤكد أن هذه الخوارزمية تحتاج إلى دعم عدد عشوائي من المجموعات التي سيتم "الانضمام إليها"، حيث أن فهم القائمة يمكن أن يشمل أي عدد من المجموعات.

Answer 1

وماذا عن شيء مثل هذا:

#!/usr/bin/perl

use strict;
use warnings;

my @list1 = qw(1 2);
my @list2 = qw(3 4);
my @list3 = qw(5 6);

# Calculate the Cartesian Product
my @cp = cart_prod(\@list1, \@list2, \@list3);

# Print the result
foreach my $elem (@cp) {
  print join(' ', @$elem), "\n";
}

sub cart_prod {
  my @sets = @_;
  my @result;
  my $result_elems = 1;

  # Calculate the number of elements needed in the result
  map { $result_elems *= scalar @$_ } @sets;
  return undef if $result_elems == 0;

  # Go through each set and add the appropriate element
  # to each element of the result
  my $scale_factor = $result_elems;
  foreach my $set (@sets)
  {
    my $set_elems = scalar @$set;  # Elements in this set
    $scale_factor /= $set_elems;
    foreach my $i (0 .. $result_elems - 1) {
      # Calculate the set element to place in this position
      # of the result set.
      my $pos = $i / $scale_factor % $set_elems;
      push @{$result[$i]}, $$set[ $pos ];
    }
  }

  return @result;
}

والتي تنتج الإخراج التالي:

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6

Answer 2

و3 مرات أسرع ويستخدم ذاكرة أقل (أقل بتدوير).

cartesian: func [
 d [block! ] 
 /local len set i res

][
 d: copy d
 len: 1
 res: make block! foreach d d [len: len * length? d]
 len: length? d
 until [
  set: clear []
  loop i: len [insert set d/:i/1   i: i - 1]
  res: change/only res copy set
  loop i: len [
   unless tail? d/:i: next d/:i [break]
   if i = 1 [break]
   d/:i: head d/:i
   i: i - 1
  ]
  tail? d/1
 ]
 head res
]

Answer 3

لمن أجل اكتمال، وإليك الجواب روبرت غامبل ترجمتها إلى REBOL:

REBOL []

cartesian: func [
    {Given a block of sets, returns the Cartesian product of said sets.}
    sets [block!] {A block containing one or more series! values}
    /local
        elems
        result
        row
][
    result: copy []

    elems: 1
    foreach set sets [
        elems: elems * (length? set)
    ]

    for n 0 (elems - 1) 1 [
        row: copy []
        skip: elems
        foreach set sets [
            skip: skip / length? set
            index: (mod to-integer (n / skip) length? set) + 1 ; REBOL is 1-based, not 0-based
            append row set/(index)
        ]
        append/only result row
    ]

    result
]

foreach set cartesian [[1 2] [3 4] [5 6]] [
    print set
]

; This returns the same thing Robert Gamble's solution did:

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6

Answer 4

وهنا هو رمز جافا لتوليد المنتج الديكارتي لعدد التعسفي من مجموعات مع عدد التعسفي من العناصر.

وفي هذه العينة قائمة "ليرة سورية" تحتوي على 4 مجموعات (LS1، LS2، LS3 وLS4) كما ترون "ليرة سورية" يمكن أن تحتوي على أي عدد من مجموعات مع أي عدد من العناصر.

import java.util.*;

public class CartesianProduct {

    private List <List <String>> ls = new ArrayList <List <String>> ();
    private List <String> ls1 = new ArrayList <String> ();
    private List <String> ls2 = new ArrayList <String> ();
    private List <String> ls3 = new ArrayList <String> ();
    private List <String> ls4 = new ArrayList <String> ();

    public List <String> generateCartesianProduct () {
        List <String> set1 = null;
        List <String> set2 = null;

        ls1.add ("a");
        ls1.add ("b");
        ls1.add ("c");

        ls2.add ("a2");
        ls2.add ("b2");
        ls2.add ("c2");

        ls3.add ("a3");
        ls3.add ("b3");
        ls3.add ("c3");
        ls3.add ("d3");

        ls4.add ("a4");
        ls4.add ("b4");

        ls.add (ls1);
        ls.add (ls2);
        ls.add (ls3);
        ls.add (ls4);

        boolean subsetAvailabe = true;
        int setCount = 0;

        try{    
            set1 = augmentSet (ls.get (setCount++), ls.get (setCount));
        } catch (IndexOutOfBoundsException ex) {
            if (set1 == null) {
                set1 = ls.get(0);
            }
            return set1;
        }

        do {
            try {
                setCount++;      
                set1 = augmentSet(set1,ls.get(setCount));
            } catch (IndexOutOfBoundsException ex) {
                subsetAvailabe = false;
            }
        } while (subsetAvailabe);
        return set1;
    }

    public List <String> augmentSet (List <String> set1, List <String> set2) {

        List <String> augmentedSet = new ArrayList <String> (set1.size () * set2.size ());
        for (String elem1 : set1) {
            for(String elem2 : set2) {
                augmentedSet.add (elem1 + "," + elem2);
            }
        }
        set1 = null; set2 = null;
        return augmentedSet;
    }

    public static void main (String [] arg) {
        CartesianProduct cp = new CartesianProduct ();
        List<String> cartesionProduct = cp.generateCartesianProduct ();
        for (String val : cartesionProduct) {
            System.out.println (val);
        }
    }
}

Answer 5

use strict;

print "@$_\n" for getCartesian(
  [qw(1 2)],
  [qw(3 4)],
  [qw(5 6)],
);

sub getCartesian {
#
  my @input = @_;
  my @ret = map [$_], @{ shift @input };

  for my $a2 (@input) {
    @ret = map {
      my $v = $_;
      map [@$v, $_], @$a2;
    }
    @ret;
  }
  return @ret;
}

والانتاج

1 3 5
1 3 6
1 4 5
1 4 6
2 3 5
2 3 6
2 4 5
2 4 6

Answer 6

يحرر: هذا الحل لا يعمل.روبرت غامبل هو الحل الصحيح.

لقد فكرت قليلاً وتوصلت إلى هذا الحل:

(أعلم أن معظمكم لا يعرف لغة REBOL، لكنها لغة سهلة القراءة إلى حد ما.)

REBOL []

sets: [[1 2 3] [4 5] [6]] ; Here's a set of sets
elems: 1
result: copy []
foreach set sets [elems: elems * (length? set)]
for n 1 elems 1 [
    row: copy []
    foreach set sets [
        index: 1 + (mod (n - 1) length? set)
        append row set/(index)
    ]
    append/only result row
]

foreach row result [
    print result
]

ينتج هذا الكود:

1 4 6
2 5 6
3 4 6
1 5 6
2 4 6
3 5 6

(عند قراءة الأرقام أعلاه لأول مرة، قد تعتقد أن هناك نسخًا مكررة.فعلتُ.ولكن لا يوجد.)

ومن المثير للاهتمام أن هذا الرمز يستخدم تقريبًا نفس الخوارزمية (1 + ((n - 1) % 9) التي نسفت الجذر الرقمي سؤال.