LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

All possible permutations (with repetition) of a 1D array given a new array size

Solved!
Go to solution

Hello,

 

I am trying to come up with an algorithm which generates a 2D array (size n^k, k) of all possible permutations (with repetition) given a 1D array (size n) and available slots (k).  The 1D input array will contain a set of unique elements (i.e. no duplicates).  Here is more detail:

 

Inputs (as an example):

1D array:  [1 2 3 4 5]

Available slots:  3

*** Therefore, n = 5; k = 3 ***

 

The algorithm would output a 2D array (size 5^3, 3):

[1 1 1

1 1 2

1 1 3

1 1 4

1 1 5 ...

5 5 3

5 5 4

5 5 5]

 

I've achieved this using nested for loops (number of for loops equal to k) (shown below), but this solution is clunky, not easily scalable, slow, etc.

Example_k3.png

 

This part of a larger program where each permutation will be evaluated.  Note that order matters; for example, [1 1 2] is different than [2 1 1] and both must be present in the 2D array.

 

I'm using Labview 2016.  Thanks for your help!

0 Kudos
Message 1 of 23
(4,604 Views)

This sounds like an Algorithm Analysis college class homework assignment?  Smiley Wink

aputman
------------------
Heads up! NI has moved LabVIEW to a mandatory SaaS subscription policy, along with a big price increase. Make your voice heard.
0 Kudos
Message 2 of 23
(4,595 Views)

I suppose it could be, but that's not my application.  

I'm iterating through multiple spring constants - the 1D array represents a specific family of springs - and am trying to use Labview to quickly generate all possible permutations of these values.  

My brute force method (nested for loops) is working fine; just wanted to reach out to see if someone had input on a more elegant (and efficient) way of doing this.

0 Kudos
Message 3 of 23
(4,581 Views)

Aren't Permutations with repetition called Combinations? nCk

Smiley Wink

Help the Community (and future reviewers) by marking posts as follows:
If it helped - KUDOS
If it answers the issue - SOLUTION
0 Kudos
Message 4 of 23
(4,565 Views)

I suspect this will involve some recursion, but I would also think it can be solved without.  And since I don't want to try to figure it out, I'll post some links.

aputman
------------------
Heads up! NI has moved LabVIEW to a mandatory SaaS subscription policy, along with a big price increase. Make your voice heard.
0 Kudos
Message 5 of 23
(4,554 Views)

using recursion..array combos.png

 

... and yes there may be a few stray wires...

Message 6 of 23
(4,542 Views)

This is slightly different to this old problem, but the way I see it, all you need is counting up to the largest possible three digit number in a Quinary system, easy to do using quotient &remainder.

 

Shouldn't take more that a postage stamp worth of code. 😄

0 Kudos
Message 7 of 23
(4,524 Views)
Solution
Accepted by topic author adamchick

@altenbach wrote:

 

Shouldn't take more that a postage stamp worth of code. 😄


Here's a quick draft. Modify as needed.

 

Also note that it works for any size input array and number of digits (within reason, of course! ;))

 

(... and yes, it took me much less time than the 14 minutes since the previous post :D)

  

 

(Note that the first loop is just a "blue" exponentiation)

 

Download All
Message 8 of 23
(4,518 Views)

The recursive solution from Mancho00 is much more elegant than the messy iterative one I was working up, and therefore won't bother posting.  

 

Recursion is efficient in terms of the quantity of source code to be maintained.  Your nested For Loop solution is probably pretty efficient for execution time (likely noticeably faster than recursion for large 1D arrays & large #'s of slots).

 

The main downside I noted in your screenshot was the need to hardcode #'s of nested loops in distinct cases and then feed a hardcoded # of branched copies of the 1D array into those loops where only some of them usually get used.  The recursive solution makes those things unnecessary.

 

All I did below was to turn Mancho00's snippet into an actual vi so I could set it up with reentrant execution properties and to make it more clear that the visible "outer" code is literally the internal contents of the "inner subvi" being called.

 

 

-Kevin P

 

 

P.S.  Too late, altenbach posted a better solution between the time I started and when I got around to finishing...

CAUTION! New LabVIEW adopters -- it's too late for me, but you *can* save yourself. The new subscription policy for LabVIEW puts NI's hand in your wallet for the rest of your working life. Are you sure you're *that* dedicated to LabVIEW? (Summary of my reasons in this post, part of a voluminous thread of mostly complaints starting here).
0 Kudos
Message 9 of 23
(4,510 Views)

I knew Altenbach would be around shortly to figure this one out.  Right up his alley of "doing more with less code".  Smiley Very Happy

aputman
------------------
Heads up! NI has moved LabVIEW to a mandatory SaaS subscription policy, along with a big price increase. Make your voice heard.
0 Kudos
Message 10 of 23
(4,491 Views)