Nhờ tư vấn thuật toán về mảng

#1

Em có cái này khó nghĩ quá nhờ các bác tư vấn giúp em.

VD: e có 2 bảng
a = {a1,a2}
b= {b1,b1]
Kết quả cần in ra là mảng
c = {a1b1, a1b2, a2b1, a2b2}

Cao hơn tí là 3 mảng
a = {a1,a2,a3}
b = {b1,b2,b3}
c = {c1,c2}
Kết quả cần in ra là mảng
d = {a1b1c1, a2b1c1, a3b1c1,…}

Chắc ví dụ thế dễ hiểu rồi ạ. Vấn đề bây giờ là em có n bảng và mỗi bảng có n giá trị khác nhau thì e phải nên làm thể nào giờ các bác tư vấn thuật toán giúp ạ.

#2

:confused: nếu bạn dùng Python thì tìm hiểu các hàm Zip() của nó nhé.

#3

Bạn định cho nạp dữ liệu ntn? 1 cho tất cả hay số tham số tùy chọn?

Cartesian product thì dùng đệ quy thôi.

^ zip() chỉ kết 1-1-… thôi.

#4

Mình không rành Python cho lắm

>>> import itertools
>>> some_list = [[1, 2], [3, 4], [5, 6]]
>>> for element in itertools.product(*some_list):
...     print(element)
...
(1, 3, 5)
(1, 3, 6)
(1, 4, 5)
(1, 4, 6)
(2, 3, 5)
(2, 3, 6)
(2, 4, 5)
(2, 4, 6)

Edit: Không thì tự viết một cái

>>> def product(a):
...     results = [[]]
...     for foo in a:
...             results = [x + [y] for x in results for y in foo]
...     for prod in results:
...             yield tuple(prod)
...
>>> for i in product([[1, 2], [3, 4, 5], [6, 7]]):
...     print(i)
...
(1, 3, 6)
(1, 3, 7)
(1, 4, 6)
(1, 4, 7)
(1, 5, 6)
(1, 5, 7)
(2, 3, 6)
(2, 3, 7)
(2, 4, 6)
(2, 4, 7)
(2, 5, 6)
(2, 5, 7)
2 Likes
#5

cái này giống hàm nhân các đa thức có số mũ khác nhau thôi bạn, dùng vòng lặp mà giải quyết, độ phức tạp thì m^n rồi.

#6

có n mảng A, mỗi mảng Ai có mi phần tử thì lặp k từ 0 tới m1 * m2 * m3 * … * mn rồi dựa vào k mà đoán xem phần tử thứ k chứa A1[a1] nào, A2[a2] nào, …, An[an] nào. Hay từ k có thể tính ra a1, a2, …, an

tạo mảng p1…pn với pn = 1, pi = pi+1 * mi+1
ta có thể tính ai = k / pi % mi

đơn giản @_@

1 Like
#7

Đây là bản Polynomial product.
https://docs.scipy.org/doc/numpy/reference/generated/numpy.polynomial.polynomial.polymul.html#numpy.polynomial.polynomial.polymul

1 Like
#8

ngon lành @_@

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

int main()
{
    std::vector<std::vector<std::string>> A = {
        {"A", "B"},
        {"1", "2", "3"},
        {"a", "b", "c", "d"}
    };
    
    int m = 1;
    for (int i = 0; i < A.size(); ++i)
        m *= A[i].size();
    
    std::vector<int> p(A.size(), 1);
    for (int i = A.size()-1; i--; )
        p[i] = p[i+1] * A[i+1].size();
    
    for (int k = 0; k < m; ++k)
    {
        for (int i = 0; i < A.size(); ++i)
        {
            int ai = k / p[i] % A[i].size();
            std::cout << A[i][ai];
        }
        std::cout << " ";
    }
}

mảng {“A”, “B”}, {“1”, “2”, “3”}, {“a”, “b”, “c”, “d”} in ra

A1a A1b A1c A1d A2a A2b A2c A2d A3a A3b A3c A3d B1a B1b B1c B1d B2a B2b B2c B2d B3a B3b B3c B3d

mảng {“1”, “2”, “3”}, {“a”, “b”, “c”, “d”}, {“A”, “B”} in ra

1aA 1aB 1bA 1bB 1cA 1cB 1dA 1dB 2aA 2aB 2bA 2bB 2cA 2cB 2dA 2dB 3aA 3aB 3bA 3bB 3cA 3cB 3dA 3dB

đếm số thôi ko có gì cao siu cả, xài thư viện chi mất công đọc doc còn lâu hơn viết ra

1 Like
#9

Thanks các bác đã nhiệt tình giúp đỡ.
Thực ra cái này em chỉ hỏi thuật toán thôi ạ.

Và tối qua em nghĩ ra được thuật toán là:

  • Chúng ta có thể nhân 2 mảng với nhau 1 cách đơn giản là dùng 2 vòng for.
  • Sau khi 2 mảng nhân với nhau thì chúng ta sẽ được 1 mảng mới và dùng mảng đó nhân với mảng thứ 3.
  • Sau đó cũng sẽ được 1 mảng mới và dùng mảng đó nhân với mảng thứ 4
  • Sau đó cũng dc 1 mảng mới và dùng mảng đó nhân với mảng thứ 5
    … :smiley:

Giống như hàm tính 1+2+3+4+5+6+7+8+9+10+11+12+…
:smiley: Không nghĩ dc thì khó, nghĩ ra được rồi thì thấy đơn giản vãi.

Thanks các bác!

#10

Cách này không hay đâu :slight_smile: vì tạo ra mảng trung gian.

Vả lại P x Q x S != (P x Q) x S :), ko giống phép cộng.

1 Like
#12

Em đang thắc mắc là cái này nó khác nhau ở trường hợp nào. Em nhân ma trận cũng không thấy nó khác Vì

PQS == (PQ)S == P(QS)

#13

Phép nhân với phép cộng giống nhau mà bác.
Nếu k làm giống 1+2+3+4+5+6+7+8+9
thì làm theo kiểu 1x2x3x4x5x6x7x8x9

#14

A, giờ mới để ý thấy:
Cái đề bài có vấn đề:

Như vậy, hàm này đếm a1 trước, khi đếm a1 thì đếm b1 rồi b2

Ở đây thì lại đếm c1 trước, rồi đếm b1, rồi đếm a1, a2…
Thế rốt cuộc thì là đếm theo thứ tự nào để anh em còn code.
Nếu làm theo thứ tự 1 thì PQR = (PQ)R
Nhưng làm theo thứ tự 2 thì PQR != (PQ)R

#15

Tính chất phân phối thì nó được ứng dụng trong tính toán song song.

Về cách giải của bác làm đúng, và cũng là cách hiện thực trong thư viện luôn. Tuy nhiên không phải làm từ trái sang phải , mỗi lần tính là có 1 mảng trung gian, mà thực hiện tính toán song song.

Ví dụ n đủ lớn, như 50. Lúc này chia ra làm 10 chunks, mỗi chunk gồm 5 mảng, chunk 0 từ mảng 0 đến 4, chunk 2 từ 5 đến 9,…

10 chunk được xử lý bởi 10 cluster. Trong 1 cluster thì tính toán nhân 5 mảng theo cách nào cũng được, thường là cách đơn giản, dễ đọc. 10 cluster sẽ chạy song song, cho ra kết quả 10 mảng.

10 mảng đó lại phân thành 2 chunk, chạy song song trên 2 cluster, ra 2 mảng. 2 mảng bỏ vào chunk mới rồi tính trên cluster tiếp ra kết quả cuối cùng.

Cluster mình nói có thể là CPU, GPU, hay đơn giản là 1 core trong CPU. Nên 1 máy tính có thể có 1 cluster hay nhiều cluster đều được.

#16

Các bạn xem lại định nghĩa tích Cartesian :slight_smile: vả lại ((1, 2), 3) != (1, 2, 3) nên (P x Q) x S != P x Q x S.

2 Likes
#17

Nghe như tích đề các trong đại số tt vậy

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?