Create a vi to read a four-digit positive integer number n and generate all the possible permutations of those numbers digit by digit. For example, n = 7812, the permutations are 7821, 8721, 8712, 2871, 2817.Labview
Answers
Answer:
Explanation:
Let's make permutations of 1,2,3. One way I am going to make the permutation is: I will start by keeping the first number, i.e. 1, fixed, and will make the permutations of the other numbers. Thus the numbers obtained by keeping 1 fixed are:
123
132
Now, we have all the numbers which can be made by keeping 1 at the first position. So, let's keep 2 at the first position this time and make the permutations.
213
231
Similarly, keeping 3 at the first position, the numbers are:
312
321
So, now we have all our permutations which can be made by the digits 1, 2 and 3. And of course, making permutations of only 3 digits is quite easy. So, let's use this logic to make the permutations of the digits 1, 2, 3 and 4. We will start by keeping 1 at the first position. Thus, we are left with the digits 2, 3 and 4. And we have to make all the permutations of the digits 2, 3 and 4. So, we will make the permutations of 2, 3 and 4 by keeping 2 fixed. Thus the numbers obtained are:
1234
1243
Now, we will fix 3 out of 2, 3 and 4.
1324
1342
Again, keeping 4 fixed out of 2, 3 and 4.
1423
1432
Now, we have all the numbers which can be made by keeping 1 at the first position. Similarly, we will keep all other digits at the first position and get the corresponding permutations. You can see that we are breaking the problem into smaller problems and then making the permutations of these smaller ones. After having all the permutations of the smaller number, we are just replacing one of the digits of this new number with the last digit which was fixed and again making permutations of the newer number. For example, After making all the permutations of 34 (34 and 43) and getting the numbers 1234 and 1243, we replaced 2 with 3 (2 was the last fixed digit in the number). Now, the last two digits are 2 and 4. Now, we made the permutation of these digits and got 1324 and 1342.
Similarly, after having the permutation of last three digits, we will replace the first digit and will again get all the permutations of the last three digits.
So, you have understood the logic of making the permutations. Now, let's the code for the same.
It can be easily noticed that for the number 1234, we are first making permutations of 234 first and for 234, permutations of 34 and so on. Thus, we are recurring to make permutations here. So, recursion seems to be the most generic way to solve the problem. So, let's make a permutation function to do this.
array = [1, 2, 3, 4]
function permutation(start, end):
#i will go from start to end
for i -> (start, end+1):
permutation(start+1,end)
Here, we have just implemented the above-stated logic. To make the permutations of 1234, we have to make the permutations of 234 first and this will be done in the first iteration (i will be 0). For this, permutation(1,3) will be called. Now in this permutation (where elements are 2, 3 and 4), we need to make the permutations of 3 and 4 first. And thus, permutation(2,3) will be called to do so. Similarly, permutation(3,3) will be called at the end. At this point, we have to make the permutations of only one digit with the index 3 and it has only one permutation i.e., itself. So, we can now print this permutation as no further recursion is now need.
array = [1, 2, 3, 4]
function permutation(start, end):
if end==start:
print array
return for i -> (start, end+1):
for i -> (start, end+1):
permutation(start+1,end)
Now, 1234 will be printed as it is the first permutation of the number 1, 2, 3 and 4. Till now, we are able to implement the logic of recursion. But we still have to write the code where the swapping of the numbers will take place. For example, after printing of 1234, we will get out of the permutation(3,3) function to the permutation(2,3) function. In the permutation(2,3) function, the loop will increase the value of 'i' and will point to the element with index 3 in the array. Also, the variable 'start' is 2 and to continue further, we need to swap these two elements as we were doing above. You can also say that the element with the index 2 was the last fixed element. So, we need to swap it with the next element. Hence, after the increment of 'i', there should be a swap function.
swap(array[start],array[i])
permutation(start+1,end)
This time as well, start is equal to end and thus, 1243 will be printed this time. We are done with the digits 3 and 4. Now, we will do the swapping with the second last fixed digit i.e., 2. But our array has been changed now and is [1, 2, 4, 3] and not [1, 2, 3, 4]. So, let's first restore the array.
swap(array[start],array[i])
permutation(start+1,end)
swap(array[start],array[i])
We simply did this by reswapping the digits. Thus, our function to write all the permutations of an array is complete now.