permutations selecting from set S containing m items, into another list with length N (N>m)

Question

I have read some number of implementations for example, What is the best way to find all combinations of items in an array?

What's nice about their implementation is many are Generic , not just array of int (or worse, array of positive int's only)

I cannot however find something that can take items which is array (Name array "S") of size m. Taking items from array "S", put them into another array "P" of size n (with n smaller than m, a common restriction I dont understand).

For example,

S = [-1, 1]

P[j] = [1,1,1,1], [1, -1, 1, 1], [1, -1, -1, 1], [1, -1, -1, -1], [-1, -1, -1, -1], ... [-1, 1, 1, -1], [1, -1, -1, 1], [-1, 1, -1, 1], [1, -1, 1, -1]

j = permutations = 0 ... pow(m,n), in this example pow(2, 4) = 16

Anything in C# or python please?

Also, time complexity...

References:

What is the best way to find all combinations of items in an array?

https://codereview.stackexchange.com/questions/194967/get-all-combinations-of-selecting-k-elements-from-an-n-sized-array?newreg=92ded52aec7b4f9aaf161db14d07ee7a

score 1 · Accepted Answer · answered Oct 01 '19 at 18:46

1

Would something like this work?

def f(ms, k):
  stack = [[m] for m in ms]
  while stack:
    next = stack.pop()
    if len(next) == k:
      yield next
    else:
      stack.extend([(next[:] + [m]) for m in ms])

print([comb for comb in f([-1, 1], 4)])

answered Oct 01 '19 at 18:46

גלעד ברקן

23,602
3
25
61

Thanks, sorry I didnt reply sooner. This is elegantly written. There's no recursion that's nice and it can handle not just mixed types arrays. However, I get a feeling time complexity more like O(pow(2,k))? – user3761555 Oct 02 '19 at 16:55
1

@user3761555 what would you expect? If we need the actual list/items, how could we have a complexity that's less? If we just want the count, I think we can have O(1) as you suggest. – גלעד ברקן Oct 02 '19 at 17:10
Question, permutation itself is not a problem that can be solved in Linear time? – user3761555 Oct 02 '19 at 17:13
@user3761555 sorry, I'm not sure I understand your original question then. Please provide one example with the exact input and output you would like from the function. I thought you wanted to generate all the possibilities. – גלעד ברקן Oct 02 '19 at 17:17
1) Is "Permutation" in the first place impossible to do in Linear time?, 2) Original motivation is find permutation "S" to brute force the problem (I understand from get go probably brute forcing is sub optimal, but I still want to try anway): https://app.codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/ – user3761555 Oct 02 '19 at 17:26
Still thank you for your solution, I will keep it. If not for above problem, it will be useful for something else. – user3761555 Oct 02 '19 at 17:26
I know that one is DP. I am just exploring the supposedly more straight forward brute force approach. – user3761555 Oct 02 '19 at 18:13
There will be use for that, if not for Codility MinSumAbs DP problem, it be handy for something else. – user3761555 Oct 02 '19 at 18:14

user3761555 · Answer 2 · 2019-10-02T18:42:28.243

Csharp version (Dont allow mixed type. Also size > 100 may crash your machine)

        static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> set, int size)
        {
            Stack<IList<T>> stack = new Stack<IList<T>>();
            foreach(var item in set)
            {
                var list = new List<T>() { item };
                stack.Push(list);
            }

            while(stack.Count>0)
            {
                var next = stack.Pop();
                if(next.Count==size)
                {
                    yield return next;
                }
                else
                {

                    foreach(var item in set)
                    {
                        var list = new List<T>();
                        list.AddRange(next);
                        list.Add(item);
                        stack.Push(list);
                    }
                }
            }
        }

To use:

            int[] possibleValues = new int[] { -1, 1 };
            var permutations = Permutations(possibleValues, 4);
            foreach(var permutation in permutations)
            {
                foreach (int x in permutation)
                {
                    Console.Write($"{x} \t");
                }
            }

score 1 · Answer 3 · answered Oct 03 '19 at 19:13

1

import itertools

size = 4

for S in list ( itertools . product ([1 , -1] , repeat = size )):

answered Oct 03 '19 at 19:13

user3761555

851
10
21

permutations selecting from set S containing m items, into another list with length N (N>m)

3 Answers3