1
$\begingroup$

Consider a set with size $n$. For instance for size 4, $\{a,b,c,d\}$, where the elements are integers. Is there a general formula for finding all the sets of products of all combinations of 1, 2, 3, and 4 of the elements?

We can easily enumerate the possibilities by hand for a small set like this: $$\{a, b, c, d\};\{ab, ac, ad, bc, bd, cd\};\{abc, abd, acd, bcd\};\{abcd\}$$

But once you start getting to $n=6$ or higher, this becomes unwieldy; calculating all 32 products is a lot, and it doubles each time.

Is there a general way to get these sets of numbers, or even sums of the sets? Or is it just something I'll need to program?

$\endgroup$
3
  • $\begingroup$ What is your goal? It's a bit strange to be interested in either these sets, or their sums. Is just their sums sufficient? $\endgroup$
    – orlp
    Jul 27, 2020 at 23:21
  • $\begingroup$ Actually, the sets themselves would be sufficient. I've since learned this is known as the power set of a set, which has helped much. $\endgroup$ Jul 29, 2020 at 3:58
  • 1
    $\begingroup$ @EricSnyder If you want the sets themselves, then you're stuck with the reality that there are up to $2^n$ elements. You can at least streamline the work by doing only one multiplication or division at a time, as opposed to recalculating each element individually. $\endgroup$
    – Théophile
    Jul 29, 2020 at 21:04

1 Answer 1

1
$\begingroup$

You could use a Gray code to encode the factors of the product: $0000$ would be the empty product, $0001$ would correspond to ${a}$, and so on, up to $1111$ for the whole thing. The basic principle of the Gray code is that one bit changes at every step, which is exactly what you need here to save work.

At each step through the Gray code, you would multiply or divide by one number, according to whether a $1$ is added or removed from the codeword.

$\endgroup$
4
  • $\begingroup$ That would still take $2^n$ steps to compute $n$ numbers (assuming he wants the sums of sets). $\endgroup$
    – orlp
    Jul 27, 2020 at 23:21
  • $\begingroup$ Well, there's no getting around the fact that there are $2^n$ products (assuming the factors share no primes). But this at least saves a bit of work. $\endgroup$
    – Théophile
    Jul 27, 2020 at 23:22
  • $\begingroup$ I would agree in the case where the OP is interested in all possible products. If the OP is interested in only the sums there should be a smarter way. $\endgroup$
    – orlp
    Jul 27, 2020 at 23:23
  • 1
    $\begingroup$ Sure. I agree that it would help to know the ultimate goal. $\endgroup$
    – Théophile
    Jul 27, 2020 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.