Algorithm for finding all possible combinations of integer numbers which their sum equals the target.

Hello,

I want to develop an algorithm which finds all the possible combinations to fill an area between 5 m^2 and 50 m^2 (integer), with blocks of size 1-10 m^2 (integer).

The rules are:

1.for every area we have option of choosing only 2 different blocks, one big one small.

2.if the big fills exactly the area we use one.

3.we are not allowed to use a number of smalls which their sum is >= big.

In order to understand better imagine that you want to put tiles in your kitchen, and you want the number and the type of each tile.

For ex. for 7 the combinations are: (7)(6,1)(5,2)(5,1,1) (4,3)(4,1,1,1) (3,2,2) (3,1,1,1,1:this cant be used because you can put 3,3,1 instead.) (2,5: this you cant because you already chose 5,2) (1,3,3) (1,2,2,2).

Below I have my code which I do not know how to finalize.

Any help is much appreciated.

target = 7 ;
for i=10:-1:1

      if (i<=target)
          if (i==target)
              disp(['(',num2str(i),')'])                           
          end
          for j=1:1:10
              if ((i+j)==target)                
                  if (i>j) % in order to exclude double entries
                      disp(['(',num2str(i),',',num2str(j),')'])
  %                    a = j/i;
  %                    for l=1:1:a
  %                        disp(['(',num2str(i),',',num2str(a),')']) 
  %                    end
                  else
                      for l=(j-1):-1:1

                      end
                  end
              end            
          end
      end           
  end

[John D'Errico]

You should probably look into the idea of the partitions of an integer. However, either your example is flawed, OR your explanation is completely unclear. The fact is, your explanation was completely unclear.

You tell us that [3 1 1 1 1] can't be used, because [3 3 1] was already taken. I'm not sure why that is true based on your explanation, but suppose it is true. Then why does [3 2 2] work, when [4 3] was already listed? Or why do you allow [4 1 1 1], when [4 3] was already in the list? And you include both [5 2] and [5 1 1]. So why was [3 1 1 1 1] not allowed?

So unless you can describe what you need more clearly, how can anyone help you? If you write a confusing description with unclear, contradictory examples, we are lost. But then I think so are you too, until you think your problem out clearly enough to explain what you need.

[Christos]

[3 1 1 1 1] can't be used with the logic of the kitchen that I mentioned. If you gonna put 1 tile 3 m^2 and 4 tiles 1m^2, you will not do it and you will use 2x3 and 1x1. You start with the big (3) until you fill the biggest possible area without, of course, to exceed it, and then you fill the remaining with the small (1). This is what you would do in your kitchen in real life, at least this is what i want. (kitchen is an example, let's say stadium).

[4 1 1 1] is allowed because you can not fill the kitchen with more than one 4m^2 tile. So if you have available only two types of tiles 4 and 1, you will use this combination.

[3 2 2]: If you have only TWO types of piles (3 and 2) available, you start with the big (3) until you fill the biggest possible area without, of course, to exceed it, and then you fill the remaining with the small (2). So, in this case, in order to fill exactly a 7m^2 kitchen you need 1x3 2x2 tiles. [4 3] is another case, if you have two other types of tiles.

Important : for every size of the kitchen, for every combination of TWO types of tiles, we examine how many of each type of tile we need to exactly fill it with an optimal way (first we fill with big and the remaining space with the small)

But if you find the algorithm for ex 25m^2 kitchen then it's the same for the others.

I think I am more clear now.

And yes I think it's integer partition, maybe with some more constraints. (only 2 types of tiles, the sum of the small type of tile should not be bigger than one big tile)

My brain is burning and I cannot find a solution, maybe it's simple and a 2nd opinion will make things much more clear.

[John D'Errico]

Complex rules ensure that no simple solution exists. However, a programmatic scheme will work, as long as you are careful.