generate combinations 1

[rsshetty]

Hi,

I am not really sure if this post is appropriate for this forum. My question is more about an algorithm.

If A has 10 resources, B has 5 and c has 10, how would I generate all possible combinations of resources allocated by them.
Also, there could be more sources, say A,B, C.....n

Thanks.

 

[SkiLift]

This may be an oversimplification, but here goes anyway:

main()
{
  int a,b,c;
  for (a=1; a<=10; a++)
    for (b=1; b<=5; b++)
      for (c=1; c<=10; c++)
        printf("{%d,%d,%d}\n", a,b,c);

}

 

[rsshetty]

Well how would I deal with N sources...I cannot possibly have N for loops.

 

[ArkM]

Use recursion, for example:

typedef struct 
{
  char* name;
  int   nres;
} User;
/* For example only: */
static User users[4] =
{
  { "A", 2 },
  { "B", 2 },
  { "C", 0 },
  { "D", 3 }
};

static void Print(const int resalloc[], int nusers)
{
  int i;
	
  for (i = 0; i < nusers; ++i)
  if (resalloc[i] >= 0)
    printf(" %d",resalloc[i]);
  else
    printf(" -");
  printf("\n");
}

static void RecEnum(const User* puser, int nusers, int resalloc[], int icurr)
{
  int i;
  int last = (icurr+1 == nusers);
	
  resalloc[icurr] = -1;
  if (puser[icurr].nres <= 0)
  {
    if (last)
      Print(resalloc,nusers);
    else
      RecEnum(puser,nusers,resalloc,icurr+1);
  }
  else
  for (i = 0; i < puser[icurr].nres; ++i)
  {
    resalloc[icurr] = i;
    if (last)
      Print(resalloc,nusers);	
    else
      RecEnum(puser,nusers,resalloc,icurr+1);
  }		
}

void Enum(const User users[], int nusers)
{
  int* p;
  int  i;

  if (nusers <= 0)
    return;
  p = (int*)malloc(sizeof(int)*nusers);
  for (i = 0; i < nusers; ++i)
    printf(" %s",users[i].name);
  printf("\n");
  RecEnum(users,nusers,p,0);
  free(p);
}

int main(int argc, char* argv[])
{
  Enum(users,4);
  return 0;
}

 

[rsshetty]

ArkM,

I thought Recursion would be an option. I just didn't know how to implement it. Also, I needed to hold the combinations and not just display it as and when generated.
Thanks a lot!!!I will try your method.
However, I wrote up this bit of code and I'd like you to look at it and tell me if its efficient in terms of memory usage, runtime and basic programming practice.
I'm still a rookie but I want to improve.

#include<stdio.h>
#include <stdlib.h>

struct stacks
{
	int *data;
	stacks *next;
};

stacks *CreateSet(int val,int tot);
void Traverse(stacks *first,int tot)
stacks *JoinSet(int val,stacks *first,int iter,int tot);
void DeallocMem(stacks *first);

main()
{
	stacks *set;
	int tot;
	int temp;
	int r[10];
	int i;
		
	tot = 4;
	
	printf("Enter the total number of sources : ");
	scanf("%d",&tot);
	
	for(int j=0;j<tot;j++)
	{
	printf("\nEnter the number of units at source %d :",j);
	scanf("%d",&r[j]);
	}
	
	while(i<tot)
	{
	   if(i==0)
	   {
	   	   temp = r[i];
		   set = CreateSet(temp,tot);
		   
	   }
	   else
	   {	   
	   	   temp = r[i];
		   set = JoinSet(temp,set,i,tot);
 	   }
	   i++;
	}
      Traverse(set,tot);
}

stacks *CreateSet(int val,int tot)
{
	stacks *current = NULL;
	stacks *first = NULL;
	stacks *prev;
	
		
	for(int i=0;i<=val;i++)
	{
		current = (stacks *)malloc(sizeof(stacks));
		current->data = (int *)malloc(tot*sizeof(int));
		current->data[0] = i;
		if(i==0)
		{
			first=current;
			prev=current;
		}
		current->next = NULL;
		prev->next = current;
		prev = current;
	}
	return(first);
}

stacks *JoinSet(int val,stacks *start,int iter,int tot)
{
	stacks *current = NULL;
	
	stacks *head = NULL;
	stacks *first = NULL;
	stacks *prev;
	int flag=0;
	int value;
	
	current = start;
	while(current!=NULL)
	{
		for(int i=0;i<=val;i++)
		{
			head = (stacks *)malloc(sizeof(stacks));
			head->data = (int *)malloc(tot*sizeof(int));
			
			for(int j=0;j<iter;j++)
			{
				head->data[j] = current->data[j];
			}
			
			head->data[iter] = i;
			
			if(flag==0)
			{
				first=head;
				prev=head;
				flag=1;
			}
			
			head->next = NULL;
			prev->next = head;
			prev = head;
		}
		
		current=current->next;
	}
	
	DeallocMem(start);
	
	return(first);
	
}

void DeallocMem(stacks *first)
{
	stacks *current;
	stacks *temp;
		
	current = first;
	
	while(current!=NULL)
	{
		temp=current->next;
		free(current);
		current = temp;
		
	}
}
void Traverse(stacks *first,int tot)
{	
	stacks *current;
	int count = 0;
	
	current = first;
	while(current!=NULL)
	{
	for(int i=0;i<tot;i++)
	{printf("%d ",current->data[i]);}
	current=current->next;
	count++;
	printf("\n");
	}
	
	printf("\n");
	printf("Total combinations = %d\n",count);
}

 

[ArkM]

Let's begin from your code.
1. It's C-like code on C++ (write struct stacks on C). There are syntax errors in it (braces. After obvious correction I can compile it but can't run: it crashes, of course...
2. Semantics: probably you try to collect (what?) data in the list of stacks (why stack? it's not a stack discipline). Your JoinSet() function destroy all before current stacks via DeallocMem() call. You destroy head of stacks (empty) chain and your Traverse() can't traverse anything.
3. I can't understand what do you want to collect (and then print) in this data chunks chain. Number of combination is simple prod of

r[0]*...*r[tot-1]

, that's all. No need to build this list for it...

If you want to generate all possible combinations of resources allocated to A, B, C (users) etc, you must design and declare appropriate data structures for the task. Logical unit of allocation is a n-tuple { res, res, ... res }. Is your structure stacks adequate? It's doubtful.

My snippet above is recursive alg: RecEnum() calls himself - it's recursion, that's all. Change my Print() logic: don't print but collect resalloc array nusers values (it's one of possible res allocation) in additional array (pass it through modified ResEnum). You may adopt your approach: allocate and link next part of total allocation table in the Print() successor (allocate 1st chunk in main, pass it to recursive Enum() via parameter)...

 

[Zyrenthian]

I think what you really need to look into is combinatorics. In the question you asked, if you are trying to find all combinations of the sources A,B,C... n first do the math and determine if it is worth it. With the way the question was asked, you need to add up all the sources and compute the factorial of the sum. The value can get quite large and that value is the total number of times through a loop *(by loop I mean one single loop determining all combinations)* If you then decide that ABC is the same as ACB,BAC,BCA,CAB,CBA then you can reduce the value.

In college, I worked on combinatoric algorithms and on a low scale, it ran pretty well. But once we decided to print out all combinations, the program slowed down substantially. Even with the sample size of 25 that you presented, you will have 15511210043330985984000000 possible combinations!!!

Matt

 

[rsshetty]

I apologize for the naming and I agree the implementation is a little C-like. It is in no-way similar to stacks.

Suppose r[0] = 2 and r[1] = 3 and r[2] = 1
***********
This is what CreateSet does:
for the first resource only ie.r[0]
{0}->{1}->{2}

return pointer to begnning of this linked list
***************

send this pointer to JoinSet with pointer to list and value of r[1]

Now r[1] = 3 ie. 0,1,2,3
{0} with 0 = {0,0} ie. data[0]=0,data[1]=0
{0} with 1 = {0,1}
{0} with 2 = {0,2}
{0} with 3 = {0,3}

...
{2} with {3}= {2,3}
deallocate memory for the initial linked list ie {0}{1}{2}
return pointer to new linked list {0,0}...{2,3}
*************
send this pointer to JoinSet again with pointer to new list and value of r[2]

Now r[2] = 1 ie. 0,1
{0,0} with 0 = {0,0,0}data[0]=0,data[1]=0,data[2]=0
{0,1} with 0 = {0,1,0}
{0,2} with 0 = {0,2,0}

...
{2,3} with 0 = {2,3,0}
{0,0} with 1 = {0,0,1}
{0,1} with 1 = {0,1,1}
{0,2} with 1 = {0,2,1}

...
{2,3} with 1 = {2,3,1}

deallocate memory for the initial linked list
ie {0,0}{0,1}{0,2}........{2,3}
return pointer to new linked list {0,0,0}->{0,0,1}..{2,3,0}->...{1,3,2}

{0,0,0}->{0,0,1}..{2,3,0}->...{2,3,1} is the final combination set.

Now, is this an efficient implementation or not.






It's always in the details.

 

[ArkM]

Obviously, it's not an efficient implementation.
Cause #1: this is evident if only from the allocate - move - deallocate sequence of the algorithm. You need exactly

N = r[0]*r[1]*...*r[tot-1]

tuples for the final combination set and you can calculate this value from the beginning. Instead of an initial memory allocation and filling this memory with proper resourse combinations you try to build a linked list of tuples (more unnecessary overheads).

Yes, for a very large N we have need of some kind of memory control (but if you want to PRINT all tuples, who will read this huge digits stream?.

It seems the alg is too expensive and complex, it's hard to understand (==debug) one (Cause #2). Now it can't work properly (memory access exception) - it's not a great surprise.

The great principle: Keep it simple...

The only question was: is it efficient? My answer: No, it's not...

 

[rsshetty]

Hmmm....
I see what you mean. Your recursive implementation is quite good. All of sudden, my implememtation looks awful. yechhh!!
That's pretty neat,ArkM.
One more question though.
If I wanted to store these combinations, what would be an appropriate data structure?


It's always in the details.

 

[SkiLift]

Are you counting how many times you loop? For exmple, say N=2, and A has 5 resources and B has 7. Let's dummy down and say that N is always 2.

for (a=1; a<=5; a++)
  for (b=1; b<=7; b++) {
    printf("{%d,%d}\n", a, b);
    cnt++;
  }
printf("cnt=%d\n", cnt);

cnt will be 5*7=35. Or you could say that our algorithm count is Resourse Count of A (rca) times Resource Count of B. Is this the fastest algorithm possible? I suspect it is, but I dont know. Since your original question was more about an algoritm, It might be a good idea to think about this. If I come up with anything, I'll report back.

 

[rsshetty]

Thanks SkiLift.
I need a very efficient algorithm because, my number of resources change dynamically and it's quite possible that there could be N resource centers.. N > 7 or 8 and each one could have more than 10-15 resources.
So you see why efficiency in terms of runtime and memory is of the utmost importance.

It's always in the details.

 

[ArkM]

Dear Rsshetty,
you (and I can't store (10..15)^(8 or more)tuples in memory! You must use more than 10 gigabytes to store this huge amount of (useful info (even if using 1 byte char for resource numbers)...

These combinative things are very crafty ones.

It seems the true problem is not of data structure or algorithmic aspect: it's use case and high-level design issue...

You may build chain (linked list) of data chunks in spirit of your stacks, but your application virtual memory may crash any computer. You may write these chunk onto disk file, but have you 10 Gb quotas on your server?...

You may generate all combinations with or without recursion: it's not a problem. The problems is: what for and where to store?...

 

[rsshetty]

ArkM,
hmmm..I see what you mean. I do have access to a server with approx 2 Gig.
Now you got me thinking ...
Thanks anyway.

rsshetty.

It's always in the details.