PermutationWrite a C function that takes an array of digits representing a number and returns a 2D array containing all possible permutations of the digits.For example, given the array [1, 2, 3], the function should return a 2D array containing the following permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].Testcase:Input:1 2 3Output:1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
Question
PermutationWrite a C function that takes an array of digits representing a number and returns a 2D array containing all possible permutations of the digits.For example, given the array [1, 2, 3], the function should return a 2D array containing the following permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].Testcase:Input:1 2 3Output:1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
Solution
Here is a C function that generates all permutations of a given array of digits:
#include <stdio.h>
void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void permute(int *a, int l, int r) {
int i;
if (l == r) {
for(i = 0; i <= r; i++)
printf("%d ", a[i]);
printf("\n");
}
else {
for (i = l; i <= r; i++) {
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); // backtrack
}
}
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
permute(arr, 0, n-1);
return 0;
}
This program uses a recursive function permute() to generate all permutations. The function takes an array of digits, and two indices l and r representing the current range to be permuted. It generates all permutations by swapping each digit with every other digit in the current range, and then recursively permuting the remaining digits.
The swap() function is used to swap two digits in the array.
The main() function initializes an array of digits and calls permute() to generate and print all permutations. The size of the array is calculated using sizeof(arr)/sizeof(arr[0]).
Please note that this program prints the permutations to the standard output. If you want to return a 2D array containing the permutations, you will need to modify the program accordingly.
Similar Questions
Permutations of all digits in a numberGiven an n-digit number(all digits are unique), write a working code to generate permutations of all numbers possible using one or more digits from the input number.Eg: Input: 123Output:123121321233132123132213231312321
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1:Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Example 2:Input: nums = [0,1]Output: [[0,1],[1,0]]Example 3:Input: nums = [1]Output: [[1]] Constraints:1 <= nums.length <= 6-10 <= nums[i] <= 10All the integers of nums are unique.
TransposeYou are developing a program for a scientific research team that works extensively with matrices. As part of a new project, the team needs a function to calculate the transpose of a given matrix. The transpose of a matrix is obtained by swapping its rows and columns.Your task is to write a C function transposeMatrix that takes a 2D array representing a matrix as input and calculates its transpose.Testcase:Input:1 2 3 4 5 6 7 8 9Output1 4 72 5 83 6 9
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).For example, the next permutation of arr = [1,2,3] is [1,3,2].Similarly, the next permutation of arr = [2,3,1] is [3,1,2].While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.Given an array of integers nums, find the next permutation of nums.The replacement must be in place and use only constant extra memory. Example 1:Input: nums = [1,2,3]Output: [1,3,2]Example 2:Input: nums = [3,2,1]Output: [1,2,3]Example 3:Input: nums = [1,1,5]Output: [1,5,1] Constraints:1 <= nums.length <= 1000 <= nums[i] <= 100
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.