How to Create Lazy Combinations

How to create lazy combinations

Here is what I came up with:

func combinations<T>(options: [[T]]) -> AnySequence<[T]> {
    guard let lastOption = options.last else {
        return AnySequence(CollectionOfOne([]))
    }
    let headCombinations = combinations(options: Array(options.dropLast()))
    return AnySequence(headCombinations.lazy.flatMap { head in
        lastOption.lazy.map { head + [$0] }
    })
}

The main difference to this solution is that the recursive
call creates a sequence
of the first N-1 options, and then combines each element of
that sequence with each element of the last option. This is more
efficient because the sequence returned from the recursive call
is enumerated only once, and not once for each element that it is
combined with.

Other differences are:

• There is no need to call .lazy on the AnySequence if that
  sequence is already lazy. The return type is therefore "simplified"
  to AnySequence<[T]>.
• I have used CollectionOfOne to create a single-element sequence
  for the empty array.
• Treating the case options.count == 1 separately is not necessary
  for the algorithm to work (but might be a possible performance
  improvement).

---

A completely different approach is to define a custom collection type
which computes each combination as a function of the index, using
simple modulo arithmetic:

struct Combinations<T> : RandomAccessCollection {
    let options: [[T]]
    let startIndex = 0
    let endIndex: Int

    init(options: [[T]]) {
        self.options = options.reversed()
        self.endIndex = options.reduce(1) { $0 * $1.count }
    }

    subscript(index: Int) -> [T] {
        var i = index
        var combination: [T] = []
        combination.reserveCapacity(options.count)
        options.forEach { option in
            combination.append(option[i % option.count])
            i /= option.count
        }
        return combination.reversed()
    }
}

No extra storage is needed and no recursion. Example usage:

let all = Combinations(options: [[1, 2], [3, 4], [5, 6]])
print(all.count)
for c in all { print(c) }

Output:

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

Testing with

let options = Array(repeating: [1, 2, 3, 4, 5], count: 5)

this collection-based method turned out to be faster then the
my above sequence-based method by a factor of 2.

Lazy combinations of c++ ranges view

Make "everything" lazy

Totally untested code

auto lazycombo = [values, comb_size]() mutable { 
  bool ok = next_combination(values.begin(), values.begin() + comb_size, values.end());
  return std::span(values.begin(), values.begin()+comb_size);
}

see next_combination.

Now using your

auto combinationIdx = ranges::views::generate(lazycombo);

Which should be generate_n as there is no way to stop generate, where the n should be the number of possible combinations.
.

Lazy combinations

Here you go. ConcatItem and Yield replace helper.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test1
{
    class Program
    {
        static void PrintOut<T>(IEnumerable<IEnumerable<T>> data)
        {
            foreach (var item in data)
            {
                string output = "-";
                if (item != null)
                    output = string.Join(",", item.Select(x => (x == null) ? "-" : x.ToString()));
                Console.WriteLine(output);
            }
        }

        static IEnumerable<T> Yield<T>(T item)
        {
            yield return item;
        }

        static IEnumerable<T> ConcatItem<T>(IEnumerable<T> enumerable, T item)
        {
            return enumerable == null ? Yield(item) : enumerable.Concat(Yield(item));
        }

        static IEnumerable<IEnumerable<T>> helper2<T>(IEnumerable<IEnumerable<T>> input) where T : class
        {
            var initalAcc = Enumerable.Empty<IEnumerable<T>>();
            var result = input.Aggregate(initalAcc,
                (acc, choiceSet) =>
                    acc.DefaultIfEmpty()
                        .SelectMany((chosen) => (choiceSet ?? Enumerable.Empty<T>()).DefaultIfEmpty().Select(choice => ConcatItem(chosen, choice)))
            );
            return result;
        }

        static void Main(string[] args)
        {
            var preCombination = new List<List<string>> { 
                new List<string> {"1","2"}, 
                new List<string> {"3"},
                new List<string> {"4","5"},
                null,
                new List<string> {"6","7"},
            };
            var postCombination = helper2(preCombination);

            PrintOut(preCombination);
            Console.WriteLine();
            PrintOut(postCombination);
            Console.ReadLine();
        }
    }
}

How can I get the length N combinations for an array using lazy evaluation?

"What I'm specifically trying to do is run a block for each element of the array.combination results, but I don't want to load up all the length-N combinations into memory first."

That is exactly what your code is doing. You are invoking the combination method without a block, which results in an Enumerator. Then you use its eachmethod. Only one combination is in memory at a time.

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!

Python: Combinations

Why do you need to reinvent the wheel? Since you've tagged python, you should know there are a ton of libraries that help you do useful things like this. One such library is itertools, more specifically the itertools.permutations function:

>>> from itertools import permutations
>>> x = [1, 2, 3, 4, 5, 6]
>>> for p in permutations(x):
...     print(p)
... 
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

If you must write an algorithm yourself, then you should learn about the Johnson-Trotter Algorithm for generating permutations. It is quite intuitive, and generates permutations in O(n!) time.

Algorithm to return all combinations of k elements from n

Art of Computer Programming Volume 4: Fascicle 3 has a ton of these that might fit your particular situation better than how I describe.

Gray Codes

An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- ²⁰C₃ = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.

Some of the original papers describing gray codes:

1. Some Hamilton Paths and a Minimal Change Algorithm
2. Adjacent Interchange Combination Generation Algorithm

Here are some other papers covering the topic:

1. An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
2. Combination Generators
3. Survey of Combinatorial Gray Codes (PostScript)
4. An Algorithm for Gray Codes

Chase's Twiddle (algorithm)

Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects' (1970)

The algorithm in C...

Index of Combinations in Lexicographical Order (Buckles Algorithm 515)

You can also reference a combination by its index (in lexicographical order). Realizing that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.

So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).

The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse – which is much trickier. This is how Buckles solves the problem. I wrote some C to compute them, with minor changes – I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n.
Note:

1. Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.
2. This method has an implicit 0 to start the set for the first difference.

Index of Combinations in Lexicographical Order (McCaffrey)

There is another way:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:

The set that maximizes , where .

For an example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires choose function, left to reader:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

A small and simple combinations iterator

The following two algorithms are provided for didactic purposes. They implement an iterator and (a more general) folder overall combinations.
They are as fast as possible, having the complexity O(ⁿC_k). The memory consumption is bound by k.

We will start with the iterator, which will call a user provided function for each combination

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

A more general version will call the user provided function along with the state variable, starting from the initial state. Since we need to pass the state between different states we won't use the for-loop, but instead, use recursion,

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

How to write a function that appends a variable number of elements to a lazy list with each iteration?

One way to look at your problem is that appendq isn't lazy enough. You can make things work if you define a function appendqf with this type:

'a seq -> (unit -> 'a seq) -> 'a seq

In other words, the second parameter isn't a sequence. It's a function that returns a sequence.

(Note that this type, unit -> 'a seq, is what actually appears inside a Cons.)

I tried this and it works for me.

Lazy n choose k in OCaml

Here is a strict and suboptimal version. I hope it is clear. It avoids duplicates by assuming there are no duplicates in the input list, and by generating only sublists that are in the same order as in the original list.

The length computation could be factored by passing l's length as an argument of choose. That would make the code less readable but more efficient.

For the lazy version, sprinkle "lazy" and "Lazy.force" on the code...

let rec choose k l =
  if k = 0 
  then [ [] ]
  else
    let len = List.length l in
    if len < k
    then []
    else if k = len
    then [ l ]
    else
      match l with
      h :: t ->
          let starting_with_h =
            (List.map (fun sublist -> h :: sublist) (choose (pred k) t))
          in
          let not_starting_with_h = choose k t in
          starting_with_h @ not_starting_with_h
      | [] -> assert false
;;
  val choose : int -> 'a list -> 'a list list = <fun>

# choose 3 [1; 2; 3; 4; 5; 6; 7] ;;                        
- : int list list =
[[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 2; 6]; [1; 2; 7]; [1; 3; 4]; [1; 3; 5];
 [1; 3; 6]; [1; 3; 7]; [1; 4; 5]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7];
 [1; 6; 7]; [2; 3; 4]; [2; 3; 5]; [2; 3; 6]; [2; 3; 7]; [2; 4; 5]; [2; 4; 6];
 [2; 4; 7]; [2; 5; 6]; [2; 5; 7]; [2; 6; 7]; [3; 4; 5]; [3; 4; 6]; [3; 4; 7];
 [3; 5; 6]; [3; 5; 7]; [3; 6; 7]; [4; 5; 6]; [4; 5; 7]; [4; 6; 7]; [5; 6; 7]]

EDIT:

A lazy_list_append as appears necessary from the comments below:

type 'a node_t =             
      | Empty
      | Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t

let rec lazy_list_append l1 l2 =
  lazy 
    (match Lazy.force l1 with
      Empty -> Lazy.force l2 
    | Node (h, lt) ->
    Node (h, lazy_list_append lt l2))
;;

---

Related Topics