Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

c++ - Algorithm to get Cartesian product

I have an array like [0,2,3,0,1] as input , and I need to find Cartesian product of {0}x{0,1,2}x{0,1,2,3}x{0}x{0,1}, more precisely I need to have output as following.


Input:

[0, 2, 3, 0, 1]

Output:

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 1]
[0, 0, 2, 0, 0]
[0, 0, 2, 0, 1]
[0, 0, 3, 0, 0]
[0, 0, 3, 0, 1]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 1]
[0, 1, 1, 0, 0]
[0, 1, 1, 0, 1]
[0, 1, 2, 0, 0]
[0, 1, 2, 0, 1]
[0, 1, 3, 0, 0]
[0, 1, 3, 0, 1]
[0, 2, 0, 0, 0]
[0, 2, 0, 0, 1]
[0, 2, 1, 0, 0]
[0, 2, 1, 0, 1]
[0, 2, 2, 0, 0]
[0, 2, 2, 0, 1]
[0, 2, 3, 0, 0]
[0, 2, 3, 0, 1]

I need a general algorithm. Any idea ? I would like to write it in c++. Thanks

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

From your example, it seem like you want to count with mixed radix, and your input is the maximum digit value for each position.

A simple way is to use arithmetic coding, treating the max digit 0 positions specially. Here's pseudo-code for the case with no 0 max digits:

input radixes
let n_numbers = product_of radixes
for i = 0 to n_numbers-1 inclusive
    let n = i
    for digit_pos = 0 to number-of-radixes-1
        output n mod radix[digit_pos]
        let n = n div radix[digit_pos]
    output newline

I leave the treatment of 0 as max digit in a position, as an exercise. :)


I can't recall any particularly relevant support for this in the C++ standard library. I.e. it's mostly a language-independent question that has nothing to do with C++, nothing to do with permutations, and nothing to do with arrays. Provided my interpretation of it is correct: it would have been better it the problem was described also with words, not just an example.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...