2

Suppose I have these two arrays

var a = new[] { "a", "b" };
var b = new[] { "1", "2", "3" };

I'm looking for a clever way (using linq or a custom linq extension method) to produce this set of results:

a b 1 2 3
a 1 b 2 3
1 a b 2 3
a 1 2 b 3
1 a 2 b 3
1 2 a b 3
a 1 2 3 b
1 a 2 3 b
1 2 a 3 b
1 2 3 a b

So I'd like to produce all the possible concatenations of fragments of both arrays without changing the order within the fragments.

Does anybody have a good idea how to implement this, maybe by using a recursive approach?

Thanks!

KarloX
  • 735
  • 8
  • 25
  • 3
    Did you try anything? – Fabio Jun 28 '21 at 06:47
  • _"maybe by using a recursive approach"_ - omg _why_ ?? – Fildor Jun 28 '21 at 06:48
  • Picked just one duplicate. This has been asked many many times and there's an abundance of solutions on Stack Overflow. – Gert Arnold Jun 28 '21 at 07:19
  • 1
    @GertArnold: This other question you're citing is something different. Actually that other question isn't very clear and the provided answers either produce tuples of two elements or take a list of n lists an produce tuples of n. I've also spent time to search stackoverflow for similar questions but I can't find one that really covers mine. So can you please remove that duplicate tag again? Thanks! – KarloX Jun 28 '21 at 07:59
  • Well, I'm sure you should be able to find an existing solution. There are really lots of similar questions. Anyway, reopened. – Gert Arnold Jun 28 '21 at 08:23
  • Or let existing solutions inspire you to find your own solution. – Gert Arnold Jun 28 '21 at 08:24
  • This question has been already answered [Question link](https://stackoverflow.com/questions/6058868/finding-all-possible-value-combinations-between-two-arrays) – Matt Qafouri Jun 28 '21 at 08:45
  • This is again a link to another question that looks similar at the first glance, but isn't really the same. That other question asks for sets or tuples of two, which is something different imho. – KarloX Jun 28 '21 at 08:49
  • StackOverflow is not a free coding service. Please share with us what have you tried so far and where did you get stuck. Without that, there is a fairly low chance that anyone will help you. – Peter Csala Jun 28 '21 at 10:10
  • Well, in no way I'm expecting free coding. But if there is a easy solution out of the box maybe someone can share it or point to a library that has it. If not, maybe someone can tell how the problem that I tried to explain using sample data can be looked at in a more formal way, so an approach for a solution may become visible and I then will try to complete it (and share the result here) – KarloX Jun 28 '21 at 10:49
  • 2
    @KarloX: Maybe this is a start: https://dotnetfiddle.net/HueTdZ But it is a very clumsy algorithm which will only work for quite short input arrays – SomeBody Jun 28 '21 at 10:51
  • Hey @SomeBody! This looks cool! How would you call this kind of algorithm? – KarloX Jun 28 '21 at 10:55
  • @KarloX I made this just up in a few minutes. Sorry, I don't know a name for that kind of problem or algorithm. I also won't post it as an answer because I think it is not good enough. – SomeBody Jun 28 '21 at 11:03
  • @SomeBody --- anyway,, great work. Thanks for this approach – KarloX Jun 28 '21 at 11:14

2 Answers2

1

Here's an elegant (but not efficient) recursive solution:

static IEnumerable<IEnumerable<T>> Interleave<T>(T[] a, T[] b)
{
    if (a.Length == 0)
    {
        yield return b;
    }
    else if (b.Length == 0)
    {
        yield return a;
    }
    else
    {
        foreach (var rest in Interleave(a[1..], b))
        {
            yield return Enumerable.Concat(new[] { a[0] }, rest);
        }
        foreach (var rest in Interleave(a, b[1..]))
        {
            yield return Enumerable.Concat(new[] { b[0] }, rest);
        }
    }
}

You can run it here.

Brian Berns
  • 15,499
  • 2
  • 30
  • 40
  • Hi @brianberns, this seems to work well. Thanks! However the solution proposed by SomeBody in the above comments is faster. – KarloX Jun 28 '21 at 18:22
  • Agreed. FWIW, I think this is mainly because array slicing is inefficient. If you switched to linked lists, I think the recursive approach would be quite fast. – Brian Berns Jun 28 '21 at 18:25
0

Based on the work of @brianberns (thanks!) I created this method which seems to be a bit faster:

public static IEnumerable<T[]> Interleave<T>(T[] input1, T[] input2)
{
    if (input1.Length == 0)
    {
        yield return input2;
    }
    else if (input2.Length == 0)
    {
        yield return input1;
    }
    else
    {
        foreach (var rest in Interleave(input1[1..], input2))
        {
            yield return new_arr(input1[0], rest);
        }
        foreach (var rest in Interleave(input1, input2[1..]))
        {
            yield return new_arr(input2[0], rest);
        }
    }

    //local method..
    static T[] new_arr(T left, T[] right)
    {
        var arr = new T[1 + right.Length];
        arr[0] = left;
        right.CopyTo(arr, 1);
        return arr;
    }
}
KarloX
  • 735
  • 8
  • 25
  • _"which seems to be a bit faster"_ - if performance is an issue, run your horses with benchmarkdotnet. – Fildor Jun 29 '21 at 07:28