Unordered Combinations of All Lengths

Unordered combinations of all lengths

You could apply a sequence the length of x over the m argument of the combn() function.

x <- c("red", "blue", "black")
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE))
# [[1]]
# [1] "red"
# 
# [[2]]
# [1] "blue"
# 
# [[3]]
# [1] "black"
# 
# [[4]]
# [1] "red"  "blue"
# 
# [[5]]
# [1] "red"   "black"
# 
# [[6]]
# [1] "blue"  "black"
# 
# [[7]]
# [1] "red"   "blue"  "black"

If you prefer a matrix result, then you can apply stringi::stri_list2matrix() to the list above.

stringi::stri_list2matrix(
    do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE)),
    byrow = TRUE
)
#      [,1]    [,2]    [,3]   
# [1,] "red"   NA      NA     
# [2,] "blue"  NA      NA     
# [3,] "black" NA      NA     
# [4,] "red"   "blue"  NA     
# [5,] "red"   "black" NA     
# [6,] "blue"  "black" NA     
# [7,] "red"   "blue"  "black"

Function to find number of 'ordered combinations' with no particular length of a list Python

As I understand your question, you want to know how many different lists there are with some subset of the elements as lst, kept in order. Since each subset can only exist in one order, the answer is simply the number of subsets: 2^n where n is the length of the list.

def count_subsets(lst):
    return 2 ** len(lst)

For example, if the list is [1, 2, 3] then there are 2^3 = 8 ordered sublists:

1. []
2. [1]
3. [2]
4. [3]
5. [1, 2]
6. [1, 3]
7. [2, 3]
8. [1, 2, 3]

If you want to exclude the empty list and/or the original list, you can simply do 2 ** len(lst) - 1 or max(0, 2 ** len(lst) - 2), as appropriate. The max(0, ...) handles the special case when your input list is empty.

---

The above handles the case like your example when the elements of the input list are all distinct. If there may be repeated elements, then the formula above overcounts. To fix it, we can use a Counter to find the number of copies of each element. If there are k copies of some element, then instead of 2 ** k combinations, we should count k + 1 sublists containing 0, 1, 2, ..., k copies.

from collections import Counter

def count_subsets(lst):
    r = 1
    for k in Counter(lst).values():
        r *= k + 1
    return r

Create combination of all elements in a list

You may try

library(dplyr)

x <- c(TRUE,FALSE)

expand.grid(x,x,x) %>%
  filter(rowSums(.) != 0) %>%
  mutate(Var1 = ifelse(Var1, "A", ""),
         Var2 = ifelse(Var2, "B", ""),
         Var3 = ifelse(Var3, "C", "")) %>%
  tibble::rownames_to_column()

  rowname Var1 Var2 Var3
1       1    A    B    C
2       2         B    C
3       3    A         C
4       4              C
5       5    A    B     
6       6         B     
7       7    A          

function

func <- function(input){
  n <- length(input)
  x <- c(TRUE,FALSE)
  
  y <- expand.grid(rep(list(x),n)) %>%
    filter(rowSums(.) != 0)
  
  for (i in 1:length(input)){
    y[,i] [y[,i]] <- input[i]
    y[,i][y[,i] != input[i]] <- ""
    
  }
  
  y %>%
    rownames_to_column()
}


inp <- c("A", "B", "C")
func(inp) 

  rowname Var1 Var2 Var3
1       1    A    B    C
2       2         B    C
3       3    A         C
4       4              C
5       5    A    B     
6       6         B     
7       7    A          

Un-ordered Combinations with limited replacements

You can use the Counter class from the collections module to find the numbers of repeats of each value in a given tuple. For each tuple, make a Counter of it and check the maximum value of the repeats. If that max value is small enough, accept the tuple; otherwise, reject it.

Here is a routine to do this. If I had more time I would pretty this up.

Be careful with this routine. For your given values of range_size=13, combo_len=7, repeat_limit=4, the result is a list of length 49,205.

from collections import Counter
from itertools import combinations_with_replacement

def unordered_combinations_with_limited_replacements(
        range_size, combo_len, repeat_limit):
    return [t for t in combinations_with_replacement(range(range_size), combo_len)
            if max(Counter(t).values()) <= repeat_limit]

print(unordered_combinations_with_limited_replacements(5, 3, 2))
print(len(unordered_combinations_with_limited_replacements(13, 7, 4)))

Here is the printout:

[(0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 3), (0, 3, 4), (0, 4, 4), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 4), (3, 4, 4)]
49205

Get all non-repeating unordered combinations of size in range

You can reduce your problem to that of finding k-multicombinations of a multiset. That is, start with a procedure that generates only subsets of size k, then vary k from minimum to maximum. Having to restart the procedure for each k isn't optimal, but given your constaints (multiset of size 1 to 30, with 1 to 8 distinct objects), this will do just fine unless your base algorithm is wildly inefficient.

You can try translating this recursive algorithm or this iterative algorithm from Python to C# with some effort.

If you don't care about the order in which the subsets are generated, then you can tweak the linked recursive algorithm to directly generate combinations with bounded cardinality:

static IEnumerable<List<T>> MultiCombinations<T>(List<T> multiset, int min, int max)
{
    Debug.Assert(min >= 0 && max >= 0);

    var a = multiset.OrderBy(x => x).ToList();

    max = Math.Min(max, a.Count);

    if (min <= max)
        foreach (var combo in Combine(a, min, max, 0, new List<T>()))
            yield return combo;
}

private static IEnumerable<List<T>> Combine<T>(List<T> a, int min, int max, int i, List<T> combo)
{
    if (i < a.Count && combo.Count < max)
    {
        combo.Add(a[i]);

        foreach (var c in Combine(a, min, max, i + 1, combo))
            yield return c;

        combo.RemoveAt(combo.Count - 1);

        var j = IndexOfNextUniqueItem(a, i);

        foreach (var c in Combine(a, min, max, j, combo))
            yield return c;
    }
    else if (combo.Count >= min)
    {
        Debug.Assert(combo.Count <= max);
        yield return new List<T>(combo);
    }
}

private static int IndexOfNextUniqueItem<T>(List<T> a, int i)
{
    int j = i + 1;

    while (j < a.Count && a[j].Equals(a[i]))
        j++;

    return j;
}

This implementation avoids generating duplicates by sorting the original input, which requires your custom objects to be comparable. But the actual algorithm itself doesn't require sorting, just the ability to group together "like" or "equal" objects.

If you can guarantee that the input list of objects will always be grouped properly, then you can remove the sorting altogether. For example:

var groupedTiles = tilesList
    .GroupBy(tile => tile.VisibleFace)
    // or .GroupBy(tile => tile, tileEqualityComparer)
    .SelectMany(grp => grp)
    .ToList();

var combos = MultiCombinationsWithoutSorting(groupedTiles);
// ...

Here I assumed the visible face of your Tile objects have a proper .Equals() method, but you can also use one of the overloads of .GroupBy() and pass in a custom IEqualityComparer. You will also have to update the IndexOfNextUniqueItem() helper method to use whatever equality test you need.

Python: Generate all uniquely ordered lists of length N

This is a combination of (a) finding lists [k_1, ..., k_n] such that each k_i equals either k_(i-1) or k_(i-1)+1, and (b) finding the unique permutations of those lists.

The first can be done using a recursive function:

def combinations(n, k=0):
    if n > 1:
        yield from ([k] + res for i in (0, 1)
                              for res in combinations(n-1, k+i))
    else:
        yield [k]

For lists with n elements, there will be 2^(n-1) such combinations:

>>> list(combinations(2))
[[0, 0], [0, 1]]
>>> list(combinations(3))
[[0, 0, 0], [0, 0, 1], [0, 1, 1], [0, 1, 2]]
>>> list(combinations(4))
[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 2], [0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2], [0, 1, 2, 3]]

Combine that with itertools.permutations and filter out duplicates to get the final result:

import itertools
def all_combinations(n):
    return (x for combs in combinations(n)
              for x in set(itertools.permutations(combs)))

Example:

>>> list(all_combinations(3))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
>>> sum(1 for _ in all_combinations(4))
75
>>> sum(1 for _ in all_combinations(5))
541

Note: Generating all n! permutations and then filtering the duplicates can be very wasteful even for slightly larger values of n. There are smarter ways of generating only unique permutations that can be used instead of itertools.permutations, see e.g. here or here.

Get all combinations of any length without sub-combinations

Ok, this should work.

from itertools import combinations

items = [("a", 1), ("b", 3), ("b", 3), ("c", 10), ("d", 15)]

res = []
for l in range(len(items), 0, -1):
    cb = combinations(items, l)
    cbl = [i for i in cb if sum([j[1] for j in i]) < 16]
    for cc in cbl:
        if not any([set(cc).issubset(el) for el in res]):
            res.append(cc)

print(res)

This prints:

[(('a', 1), ('b', 3), ('b', 3)), (('a', 1), ('b', 3), ('c', 10)), (('d', 15),)]

Please note that this code may be slow if you have a lot of items, because it iterates many times to check if a given combination is not a subset of any already accepted combination. Maybe there are more efficient solutions.

---

Related Topics