Member Avatar for MarounMaroun

Hello folks,
How can I fill a 2D-array (of size [1260][4]) with all variations of 1-10 (which is 5040 variations)?

1 2 3 4
1 2 3 5
1 2 3 6
..
..
1 7 4 9
..


and so on..

Thanks!

Edited by MarounMaroun because: n/a
  • 5 Contributors
  • 9 Replies
  • 109 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by frogboy77

Dani AI

Generated

The problem is to enumerate every ordered selection of size k from a pool of n distinct items and put each selection into one row. raised the question; and correctly pointed toward the combinatorics and STL helpers, and suggested random sampling (which does not reliably produce a full, nonrepeating enumeration). Two practical patterns that work well in real code are: (A) a simple recursive backtracking generator that yields one row at a time (best when you want to stream/process results), and (B) a two-step STL approach that picks combinations then permutes each chosen group (useful when you prefer iterative code).

Here is a straightforward C++ backtracking pattern you can adapt; call the callback for each found row so you can print, write to disk, or push into a container without needing to store everything at once.

void gen_k_perm(const std::vector<int>& pool, int k,
                std::vector<int>& out, std::vector<char>& used,
                std::function<void(const std::vector<int>&)> onFound) {
    if ((int)out.size() == k) {
        onFound(out);
        return;
    }
    for (int i = 0; i < (int)pool.size(); ++i) {
        if (used[i]) continue;
        used[i] = 1;
        out.push_back(pool[i]);
        gen_k_perm(pool, k, out, used, onFound);
        out.pop_back();
        used[i] = 0;
    }
}

If you prefer an iterative STL route: iterate combinations using a boolean selection mask and std::next_permutation, collect the selected elements, then iterate their permutations with std::next_permutation. See the next_permutation reference for details: std::next_permutation.

A compact Python generator alternative (yields each row lazily) is simple to write, or use itertools.permutations if available; see the docs: itertools.permutations.

Notes and cautions: prefer streaming (process or write each row) instead of keeping all rows in memory unless you have calculated and reserved the needed capacity. Recursion depth equals k so it is safe for modest k. If you need random access by index, convert the lexicographic index to a permutation via the factorial-number system; see Factorial number system.

Recommended Answers

All 9 Replies

Member Avatar for mrnutty

>>all variations of 1-10

There are 10! different variations go through them like so :

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

and so on

Member Avatar for MarounMaroun

there are 5040 variations.

n!/(n-k)! n=10, k=4. --> 5040

can't be two equal numbers in each series.
so it will look:

1. 1 2 3 4
2. 1 3 2 4
3. 1 3 4 2
4. ......
5. ......
.
.
.
.
5040. 4 2 1 3 (for example)

Member Avatar for FutureWebDev

Isn't 10C4 = 210

Where are you getting 5040?

I know this probably doesn't help but I was just curious as to where
you got the number 5040 from.

Member Avatar for MarounMaroun

it is 10!/6! which is 10•9•8•7 which is 5040.

think about it this way:
you have two cells, you want to fill it with all the permutations of 1-3. you'll get:

1 2
1 3
2 3
2 1
3 1
3 2

6 options, because 3!/(3-2)! is equal to 6.

if you make this calc for 10 and 4 you'll get 5040

Member Avatar for frogboy77

There are 210 ways to choose 4 from 10 but there are 24 permutations of each therefor 5040 is correct.

How is your 2D-array (of size [1260][4]) going to hold 5040 combinations?

Member Avatar for MarounMaroun

1260 rows.. 4 columns each.
so each row will hold a permutation.

anyone has an idea of how to implement such a thing?

Member Avatar for Freude

Maybe it is not best solution. Try to use random number generator for integers. Generate randomly the number from 1 to 9. Then generate second number and compare it with previous one. If it coincide, generate one more and so on till you get four different numbers. After that repeat this procedure and check whether new number is coincided with existed ones if you need that.

Edited by Freude because: n/a
Member Avatar for mrnutty

This is what you are after possibly.

Member Avatar for frogboy77

I don't think next_permutation would work. It will give you the 24 permutations once you have generated the 4-digit number but it won't generate the numbers themselves.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.