Hello Everybody,
Can anybody help me in writing a C program to generate and print all
possible combinations of n numbers.
For eg. for 3 numbers(1,2,3) there turn out 3! combinations.
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). 6 3561
Rajesh wrote: Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Show us what you've come up with so far.
Rajesh <ra***********@gmail.com> wrote: Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Yes, I can. I assume you have given it a try already, so a good start
would be for you to show us the code you have written so far.
--
:wq
^X^Cy^K^X^C^C^C^C
Rajesh wrote: Hello Everybody,
Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Well, here's something to play with, and think about. However, I don't
believe this is what you're asking for [an arbitrary value of n being
required?], but it may give you some ideas?
void perm(int n)
{
int i, k, j, d = 0;
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
for(k = 1; k <= n; ++k)
printf("%4d (%d, %d, %d)\n", ++d, i, j, k);
}
The code above will produce all the possible 'triples' of n, e.g., if n is
4, you'll still get 4! outputs, but they'll be of this form:
1 (1, 1, 1)
2 (1, 1, 2)
3 (1, 1, 3)
4 (1, 1, 4)
5 (1, 2, 1)
6 (1, 2, 2)
7 (1, 2, 3)
...
...
58 (4, 3, 2)
59 (4, 3, 3)
60 (4, 3, 4)
61 (4, 4, 1)
62 (4, 4, 2)
63 (4, 4, 3)
64 (4, 4, 4)
However, I imagine you'd really like quads for n = 4 ...
1 (1, 1, 1, 1)
2 (1, 1, 1, 2)
3 (1, 1, 1, 3)
4 (1, 1, 1, 4)
5 (1, 1, 2, 1)
6 (1, 1, 2, 2)
7 (1, 1, 2, 3)
8 (1, 1, 2, 4)
61 (4, 4, 4, 1)
62 (4, 4, 4, 2)
63 (4, 4, 4, 3)
64 (4, 4, 4, 4)
As I say, I imagine that your program *should* be able to work with
arbitrary values of 'n' [within the limits of sizeof int etc], e.g., using a
fixed number of nested loops like this is not possible - you'll have to
perhaps think recursively about the problem in that case.
--
==============
*Not a pedant*
==============
pemo wrote: As I say, I imagine that your program *should* be able to work with arbitrary values of 'n' [within the limits of sizeof int etc]
Given how fast factorial grows, it is not possible to handle cases
where n is larger than 15...
In article <dr**********@news.ox.ac.uk> "pemo" <us***********@gmail.com> writes: Rajesh wrote: Hello Everybody,
Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Well, here's something to play with, and think about. However, I don't believe this is what you're asking for [an arbitrary value of n being required?], but it may give you some ideas?
Not really. To get all permutations sequentially you have to realise
that the best way to notate a permutation is in mixed base. The last
digit is in base n, the last but one in base n-1, etc. But here is
something:
#include <stdio.h>
int fac(int n) { if(n == 0) return 1; return n * fac(n - 1); }
int perm[N], used[N];
int num_to_perm(int num) {
int i, k, d;
for(i = 0; i < N; i++) used[i] = 0;
perm[0] - 0;
for(i = 1; i < N; i++) {
k = num % (i + 1); num = num / (i + 1); perm[i] = k;
}
for(i = N - 1; i >= 0; i--) {
d = perm[i]; k = 0;
while(used[k] || d > 0) if(!used[k++]) d--;
used[k] = 1; printf("%3d", k + 1);
}
printf("\n");
}
int main(void) {
int i, max;
max = fac(N); for(i = 0; i < max; i++) num_to_perm(i);
}
Compile with -DN=n, where n is the number of elements in a permutation.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Hello Rajesh,
Here is something to play with:
#include <stdio.h>
#define N 5
int main(char *argv[],int argc)
{
char list[5]={'a','b','c','d','e'};
permute(list,0,N);
return(0);
}
void permute(char list[],int k, int m)
{
int i;
char temp;
if(k==m)
{
/* PRINT A FROM k to m! */
for(i=0;i<N;i++){printf("%c",list[i]);}
printf("\n");
}
else
{
for(i=k;i<m;i++)
{
/* swap(a[i],a[m-1]); */
temp=list[i];
list[i]=list[m-1];
list[m-1]=temp;
permute(list,k,m-1);
/* swap(a[m-1],a[i]); */
temp=list[m-1];
list[m-1]=list[i];
list[i]=temp;
}
}
}
Cheers
Shastri
Rajesh wrote: Hello Everybody,
Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Talin |
last post by:
I'm sure I am not the first person to do this, but I wanted to share
this: a generator which returns all permutations of a list:
def permute( lst ):
if len( lst ) == 1:
yield lst
else:
head =...
|
by: Jack Middleton |
last post by:
Hi!
I'm lookin for a faster permutation algorithm for matrices. I know that
it can be done with multiplying a matrix with a permutation matrix. It
just seems a waste to iterate through all those...
|
by: user |
last post by:
Hello
I have Array of 50 ints. I want to receive random permutation, so
in each int will be different number from 0-49.
Is there any class for permutation ?
Thanx
Michal
|
by: rrs.matrix |
last post by:
this is my version of permutation and combinations.
is this piece of code correct.
#include<stdio.h>
int a={1,2,3,4};
permute(int * b,int n)
{
int i;
|
by: whitehatmiracle |
last post by:
Dear Sir I couldnt quite figure out wat your permute function does
exactly... could you please throw some light on it?
void Permute(char *Perm,
size_t n,
size_t unchanged)
{
size_t outer = 0;...
|
by: weidongtom |
last post by:
Hi,
I have been working at this problem, and I think I need a permutation
algorithm that does
the following:
Given a list of elements that are either a character or a character
follows by a...
|
by: badcrusher10 |
last post by:
Hello.
I'm having trouble figuring out what to do and how to do.. could someone explain to me what I need to do in order to work?
THIS IS WHAT I NEED TO DO:
Professor Snoop wants a program...
|
by: xirowei |
last post by:
Let's say i create a String array that store 4 Alphabets {"A","B","C","D"}
How can i get the result if i need permutation of 4P3 and 4P2?
I had refer to many examples from the internet, but...
|
by: 249740 |
last post by:
Write a program that reads N phrases and determines if one phrase is a
permutation of the other. For example: Phrase 1 is: “One World One Dream” Phrase 2 is: “World One One Dream”. Then the output...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |