Print Out All Combinations of Index

print out all combinations of index

You may do:

bool increase(const std::vector<std::vector<int>>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] >= v[index].size()) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

void do_job(const std::vector<std::vector<int>>& v,
            const std::vector<std::size_t>& it)
{
    for (std::size_t i = 0; i != it.size(); ++i) {
        // TODO: manage case where v[i] is empty if relevant.
        std::cout << v[i][it[i]] << " ";
    }
    std::cout << std::endl;
}

void iterate(const std::vector<std::vector<int>>& v)
{
    std::vector<std::size_t> it(v.size(), 0u);

    do {
        do_job(v, it);
    } while (increase(v, it));
}

Live Demo

Python itertools.combinations: how to obtain the indices of the combined numbers

You can use enumerate:

>>> a = [7, 5, 5, 4]
>>> list(itertools.combinations(enumerate(a), 2))
[((0, 7), (1, 5)), ((0, 7), (2, 5)), ((0, 7), (3, 4)), ((1, 5), (2, 5)), ((1, 5), (3, 4)), ((2, 5), (3, 4))]
>>> b = list((i,j) for ((i,_),(j,_)) in itertools.combinations(enumerate(a), 2))
>>> b
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

How to get combination by index from a list of unique combinations

For larger alphabets this algorithm is much faster than generating all combinations with itertools, but there is probably still a lot of potential for optimizations:

from math import factorial

def get_combination(alphabet, index):
    """Finds the nth combination of any length"""
    alphabet = list(alphabet)
    n = len(alphabet)
    k = 0

    # Find length of combination (k)
    while k <= n:
        combination_count = n_choose_k(n, k)
        if index < combination_count:
            # index is within combinations of length k
            break
        else:
            # index is within combinations of length > k
            index -= combination_count
            k += 1
    if k > n:
        raise Exception("Index out of range")

    return get_k_combination(alphabet, int(k), index)

def get_k_combination(alphabet, k, index):
    """Finds the nth combination of length k"""
    combination = []
    for elem in range(k):
        n = len(alphabet) - 1
        k_ = k - elem - 1
        i = 0
        while n - i >= k_:
            combination_count = n_choose_k(n - i, k_)
            if index < combination_count:
                combination.append(alphabet[i])
                alphabet = alphabet[i + 1:]
                break
            else:
                index -= combination_count
                i += 1
    return combination

def get_combination_bruteforce(alphabet, index):
    return list(
        [
            x
            for i in range(len(alphabet)+1)
            for x in combinations(alphabet, i)
        ][index]
    )

def n_choose_k(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k))

Small CLI and benchmarks here

For an alphabet of length 15, get_combination took 0.228s and get_combination_bruteforce took 39.525s to find all possible combinations one by one (173 times speedup).

It works by first finding out how long the combination with the given index is and then reconstructing it element-wise:

1. The combinations are primarily sorted by length and we know that there are n over k combinations of length k, where n is the alphabet size. So we find the length by subtracting n over k for increasing k from the given index until it goes negative. The last k is the length of the requested combination.
2. Since the combinations are secondarily sorted by the alphabet order, we know that each element in a combination is only followed by higher elements. So for a combination of length k starting with the x-th element of the alphabet, the remaining combination elements have to be chosen from alphabet[x+1:]. With this information we can reconstruct each element like we calculated k before.

There may be a closed form solution to both of these steps, but I won't be the one to find it.

I'm trying to understand how to print all the possible combinations of a array

Try to group the variables into pieces that are easier to understand e.g.

int values_left_to_print = r - index; // (size of combination to be printed) - (current index into data)
int values_left_in_array = end - i + 1; // number of values left until the end of given arr

Now we can interpret it like this:

for (int i = start; i <= end && (values_left_in_array >= values_left_to_print); i++)  
{

so if i is near the end of the given array and there are not enough values left to print a full combination, then the loop (and function) will stop. Let's look at an example:

Given

arr = {1,2,3,4}
n = 4; // size of arr
r = 3; // size of combination

The top level function will start to form a combination with 1 and then with 2 resulting in (1,2,3), (1,2,4), (1,3,4)

It will not try 3 and 4, because (values_left_in_array < values_left_to_print).

If the condition was not there, then the function would try 3 and 4, but the values in the sequence only ever increase in index from left-to-right in the given array, so the combination will end because i will reach end before being able to find 3 values.

fastest way in python to enumerate all combinations and return the index

Using itertools.combinations

To get all the possible binary lists of length 5 with 3 ones

N = 5
zeros = [0]*N
for comb in itertools.combinations(range(N), r = 3):
    l = zeros.copy()
    for indice in comb:
        l[indice] = 1

Not very efficient, but should be fast enough.

To get the "big list" of indices, use itertools.combinations(range(5), 3))

Get all combinations of element from a list, including all different orders & writing it in 2 different ways

You can use itertools.permutations to build up a list of lists containing all the combinations of the items for all the possible 'lengths' as follows (the extra list(chain.from_iterable(...)) is just there to flatten things down a level:

from itertools import chain, permutations

data = ['A', 'B', 'C']
result = list(chain.from_iterable([permutations(data, x) for x in range(len(data)+1)]))

[(), ('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

To map this onto numerical positions, you can use `data.index(string) to find its position. I'm not 100% if this is what you mean, but something like the following should get you there...

numbers = []
for item in result:
    new_list = []
    for entry in item:
        # Fill the new list with the index of each letter seen.
        new_list.append(data.index(entry))
    # Pad out the rest of the list with -1
    new_list += [-1] * (len(data) - len(new_list))
    numbers.append(new_list)

print(numbers)

[[-1, -1, -1], [0, -1, -1], [1, -1, -1], [2, -1, -1], [0, 1, -1], [0, 2, -1], [1, 0, -1], [1, 2, -1], [2, 0, -1], [2, 1, -1], [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

How to get all possible combinations of a list’s elements?

Have a look at itertools.combinations:

itertools.combinations(iterable, r)

Return r length subsequences of elements from
the input iterable.

Combinations are emitted in lexicographic sort order. So, if the
input iterable is sorted, the
combination tuples will be produced in
sorted order.

Since 2.6, batteries are included!

How to know combination of elements from its index in list of all combionations in python

Here's a way to generate a pair directly from its index. There's probably a more efficient equation for this, but this is what I came up with after a couple of minutes. :)

import itertools

def pair_from_index(a, i):
    m = n = len(a) - 1
    while i >= n:
        i -= n
        n -= 1
    m -= n
    return a[m], a[m + i + 1]

# test

a = list('abcdefg')

for i, t in enumerate(itertools.combinations(a, 2)):
    print(i, t, pair_from_index(a, i))

output

0 ('a', 'b') ('a', 'b')
1 ('a', 'c') ('a', 'c')
2 ('a', 'd') ('a', 'd')
3 ('a', 'e') ('a', 'e')
4 ('a', 'f') ('a', 'f')
5 ('a', 'g') ('a', 'g')
6 ('b', 'c') ('b', 'c')
7 ('b', 'd') ('b', 'd')
8 ('b', 'e') ('b', 'e')
9 ('b', 'f') ('b', 'f')
10 ('b', 'g') ('b', 'g')
11 ('c', 'd') ('c', 'd')
12 ('c', 'e') ('c', 'e')
13 ('c', 'f') ('c', 'f')
14 ('c', 'g') ('c', 'g')
15 ('d', 'e') ('d', 'e')
16 ('d', 'f') ('d', 'f')
17 ('d', 'g') ('d', 'g')
18 ('e', 'f') ('e', 'f')
19 ('e', 'g') ('e', 'g')
20 ('f', 'g') ('f', 'g')

---

Here's an improved version that's about 10 times faster than the previous one on lists of length 500, and it should be even more efficient on larger lists.

def pair_from_index(a, i):
    n = len(a) - 1
    m = n * (n + 1) // 2
    y = m - i - 1
    d = 1 + int(((8*y + 1) ** 0.5 - 1) / 2)
    k = n - d
    return a[k], a[1 + i + k + d * (d + 1) // 2 - m]

I won't try to explain completely how it works, but it uses triangular numbers.

Let T(x) be the x'th triangular number, i.e., the sum of the numbers from 1 to x. The formula for T(x) is simple:

T(x) = x * (x + 1) / 2

Given y = T(x) we can calculate x by inverting the above formula

x = (8*y + 1) ** 0.5 - 1) / 2

Python itertools.combinations: how to obtain the indices of the combined numbers within the combinations at the same time

@Maf - try this, this is as @jonsharpe suggested earlier, use zip:

from pprint import pprint
from itertools import combinations

 my_list = [7, 5, 5, 4]
>>> pprint(list(zip(combinations(enumerate(my_list),2), combinations(my_list,2))))
[(((0, 7), (1, 5)), (7, 5)),
 (((0, 7), (2, 5)), (7, 5)),
 (((0, 7), (3, 4)), (7, 4)),
 (((1, 5), (2, 5)), (5, 5)),
 (((1, 5), (3, 4)), (5, 4)),
 (((2, 5), (3, 4)), (5, 4))]

Find all combinations that include a specific value where all values are next to each other in array

This problem could be solved in O(n^3) time-complexity using the following algorithm:

Step-1: Find the index of the target element.

Step-2: Iterate through an index of the target to the rightmost index. Let's call this iterator as idx.

Step-3: Then iterate from the target index to the leftmost index. Let's call this index as i.

Step-4: Print all the elements between the indices idx and i.

Following the above steps will print all the combinations.

The code for the above algorithm is implemented using python below.

def solution(array,target):
    
    index = -1
    for idx,element in enumerate(array):
        if(element == target):
            index = idx
            
    n = len(array)
    
    for idx in range(n-1,index-1,-1):
        for i in range(index,-1,-1):
            for j in range(i,idx+1):
                print(array[j],end = ",")
            print()
        

arr = [5, 4, 2, 0, 1, 3]
target = 0
solution(arr,target)

---

Related Topics