# [Math]Combination of words

26 replies27.02.12 04:42:41 pm

Can someone help me to solve this:

Atk - 1 combination

Atk, Magic - 3 combinations (Atk,Magic,Atk+Magic)

Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,Atk+Magic+Hp)

I need to find the possible combination for 10 words. Note that you can't use the same word again in a combination( after you use Atk+Magic, you can't use Magic+Atk)

Atk - 1 combination

Atk, Magic - 3 combinations (Atk,Magic,Atk+Magic)

Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,Atk+Magic+Hp)

I need to find the possible combination for 10 words. Note that you can't use the same word again in a combination( after you use Atk+Magic, you can't use Magic+Atk)

Cs2d tibia tutorial ================ My new CS2D RPG Project Video

Erhm...

You mean,add 1 more combination so there was 10? Looks like a little dumby

Then,

Just add defense (or whatsoever),and thats all.

Here you are,10 words. Or you mean something another?..

[EDIT]

Also,is it for script?

You mean,add 1 more combination so there was 10? Looks like a little dumby

Then,

Code:

1

Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense.)

Just add defense (or whatsoever),and thats all.

Here you are,10 words. Or you mean something another?..

[EDIT]

Also,is it for script?

edited 1×, last 27.02.12 06:17:33 pm

Nexmann: I am trying to help

He just cant explain the question.

[EDIT]

If Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,

Then,its impossible to make 10 combinations.

As I said,

But,its wrong.

That means,that you can get 1 - 3 - 7 - 13 combinations.

Or,am I again wrong?

Nah,

He just cant explain the question.

[EDIT]

If Atk, Magic, Hp - 7 combinations (Atk,Magic,Hp,Atk+Magic,Att+Hp,Magic+Hp,

**Atk+Magic+Hp**)Then,its impossible to make 10 combinations.

As I said,

Code:

1

Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense.)

But,its wrong.

Code:

1

Atk,Magic,HP,Defense (Atk,Magic,HP,Defense,Atk + Magic,Atk + HP,Atk + Defense,Magic + HP,Magic + Defense,HP + Defense,Atk+Magic+HP,Magic+HP+Defense,Atk+HP+Defense.)

That means,that you can get 1 - 3 - 7 - 13 combinations.

Or,am I again wrong?

Nah,

**Honestly,I am sucking at maths**edited 1×, last 28.02.12 12:01:15 am

Err, I'm not sure if this will do what you want, but to find the amount of possible combinations of objects you'll have to use something called a factorial. If you have 4 objects: A, B, C, D, and you want to find out all possible combinations of those objects, that will be 4! = 24. But since you have it so that you can't do the same in reverse order, i.e. if AB was used BA cannot be used already, it's going to be more than that... I'm kind of useless when it comes to this, to be honest. The Lua factorial function though is as follows:

Code:

1

2

3

4

5

6

7

8

9

2

3

4

5

6

7

8

9

function math.factorial(n)

local x=n

local r=1

while x>0 do

r=r*x

x=x-1

end

return r

end

local x=n

local r=1

while x>0 do

r=r*x

x=x-1

end

return r

end

I code, therefore I exist. | Visit my blog for Lua tips and other interesting info

**EngiN33R has written:**

Err, I'm not sure if this will do what you want, but to find the amount of possible combinations of objects you'll have to use something called a factorial. If you have 4 objects: A, B, C, D, and you want to find out all possible combinations of those objects, that will be 4! = 24. But since you have it so that you can't do the same in reverse order, i.e. if AB was used BA cannot be used already, it's going to be more than that... I'm kind of useless when it comes to this, to be honest. The Lua factorial function though is as follows:

Code:

1

2

3

4

5

6

7

8

9

2

3

4

5

6

7

8

9

function math.factorial(n)

local x=n

local r=1

while x>0 do

r=r*x

x=x-1

end

return r

end

local x=n

local r=1

while x>0 do

r=r*x

x=x-1

end

return r

end

Looks like I've just broked my brains

In lua script it looks a little easier.

But,I wonder,what he wants from this?

Well , if you want to know how much of those combinations you can do, just use (2^x)-1, were x its the number of words you want to put. In case of being 10 words it would be (2^10)-1 = 1023 combinations. Of course, this wont give you the combinations, it just tells you how much you can get.

Edit: @enginer the factorial would work if he wanted all variations of words you can do caring about the order. But he want how much subsets can be made from the words, not caring about the order.

Edit: @enginer the factorial would work if he wanted all variations of words you can do caring about the order. But he want how much subsets can be made from the words, not caring about the order.

Paradox

@ DarkLight66: I may not understand you clearly, but he said that if there are three words, let them be denominated as A, B and C, the following combos can be made:

A,B,C,AB,AC,BC,ABC

So I guess he does care about the order.

A,B,C,AB,AC,BC,ABC

So I guess he does care about the order.

I code, therefore I exist. | Visit my blog for Lua tips and other interesting info

So given the following definition of 'choosing' as

where order matters (so 'abc' is classified the same as 'bac'), then there are different combinations.

For the n=10 case, there are 1023 different combinations.

where order matters (so 'abc' is classified the same as 'bac'), then there are different combinations.

For the n=10 case, there are 1023 different combinations.

IMHO it's pretty clear, he just wants a function that for a given set, returns all it's possible sub sets excluding the empty set.

Look on power sets.

Edit: here are two implementations in Lua: http://rosettacode.org/wiki/Power_set#Lua

Look on power sets.

Edit: here are two implementations in Lua: http://rosettacode.org/wiki/Power_set#Lua

edited 1×, last 28.02.12 01:30:50 am

To generate this set, notice that if we define the subproblem of finding all combinations of a set of rank n, then

subproblem({1,2,3},2) = {1,2},{1,3},{2,3} = {1,2},{1,3}, subproblem({2,3},2)

subproblem({0,1,2,3},3) = {0,1,2},{0,1,3},{0,2,3}, subproblem({1,2,3},3)

= {0 + subproblem({1,2,3},2)}, subproblem({1,2,3},3)

subproblem(set, n) = {set[1] + subproblem(set[1:], n-1)}, subproblem(set[1:], n)

using your test code

You can optimize by noticing that subproblem's index increases monotonically, so if we cache certain indices, we can do this in O(n*n^2) time ~= a few thousand operations total.

subproblem({1,2,3},2) = {1,2},{1,3},{2,3} = {1,2},{1,3}, subproblem({2,3},2)

subproblem({0,1,2,3},3) = {0,1,2},{0,1,3},{0,2,3}, subproblem({1,2,3},3)

= {0 + subproblem({1,2,3},2)}, subproblem({1,2,3},3)

subproblem(set, n) = {set[1] + subproblem(set[1:], n-1)}, subproblem(set[1:], n)

Code:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

function subproblem(set, n)

-- base case is when n>#set

if n > #set then return {} end

if n == 1 then

local solution = {}

for _,v in ipairs(set) do

table.insert(solution, {v})

end

return solution

end

-- 1 + subproblem(set[1:],n-1)

local solution = {}

local next = {unpack(set)}

table.remove(next,1)

for _,v in ipairs(subproblem(next,n-1)) do

table.insert(solution, {set[1], unpack(v)})

end

next = {unpack(set)}

table.remove(next,1)

for _,v in ipairs(subproblem(next, n)) do

table.insert(solution,v)

end

return solution

end

function solve(set)

local solution = {}

for i=1,#set do

for _, item in ipairs(subproblem(set,i)) do

table.insert(solution,item)

end

end

return solution

end

-- base case is when n>#set

if n > #set then return {} end

if n == 1 then

local solution = {}

for _,v in ipairs(set) do

table.insert(solution, {v})

end

return solution

end

-- 1 + subproblem(set[1:],n-1)

local solution = {}

local next = {unpack(set)}

table.remove(next,1)

for _,v in ipairs(subproblem(next,n-1)) do

table.insert(solution, {set[1], unpack(v)})

end

next = {unpack(set)}

table.remove(next,1)

for _,v in ipairs(subproblem(next, n)) do

table.insert(solution,v)

end

return solution

end

function solve(set)

local solution = {}

for i=1,#set do

for _, item in ipairs(subproblem(set,i)) do

table.insert(solution,item)

end

end

return solution

end

using your test code

Code:

1

2

2

> see(solve({'atk','magazine','hp'}))

{{atk}, {magazine}, {hp}, {atk, magazine}, {atk, hp}, {magazine, hp}, {atk, magazine, hp}}

{{atk}, {magazine}, {hp}, {atk, magazine}, {atk, hp}, {magazine, hp}, {atk, magazine, hp}}

You can optimize by noticing that subproblem's index increases monotonically, so if we cache certain indices, we can do this in O(n*n^2) time ~= a few thousand operations total.

Lol, you guys are making it kinda too complicated (idk about other people but for me)

I'm sorry if my question wasn't clear, I was in a rush because I had to go to school.

BTW, Replies:

@ BlazingStan:

Thanks for your helps, but I explained that to 3 of my friends and they all understood.

@ MAX-russia: Did you even try? And not possible?

@ Alistaire: What's your point? Same as my response to Blazer, I explained that to 3 of my friends and they all understood. Flacko also said that it was clear.

@ Anders4000: Same as aboves

I'm sorry if my question wasn't clear, I was in a rush because I had to go to school.

BTW, Replies:

@ BlazingStan:

**Quote:**

He just cant explain the question.

Thanks for your helps, but I explained that to 3 of my friends and they all understood.

@ MAX-russia: Did you even try? And not possible?

@ Alistaire: What's your point? Same as my response to Blazer, I explained that to 3 of my friends and they all understood. Flacko also said that it was clear.

@ Anders4000: Same as aboves

edited 12×, last 28.02.12 03:08:24 am

Cs2d tibia tutorial ================ My new CS2D RPG Project Video

For the 4 case, we have the following possible combinations:

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

Try 2^n - 1 instead as your formula.

Code:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

a

b

c

d

ab

ac

ad

bc

bd

cd

abc

abd

acd

bcd

abcd

b

c

d

ab

ac

ad

bc

bd

cd

abc

abd

acd

bcd

abcd

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

Try 2^n - 1 instead as your formula.

**Lee has written:**

For the 4 case, we have the following possible combinations:

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

Try 2^n - 1 instead as your formula.

Code:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

a

b

c

d

ab

ac

ad

bc

bd

cd

abc

abd

acd

bcd

abcd

b

c

d

ab

ac

ad

bc

bd

cd

abc

abd

acd

bcd

abcd

This is already a contradiction to your formula as there are 15 different combinations in here in addition to null (equivalent to not choosing).

Try 2^n - 1 instead as your formula.

Yes, I just realized that after i posted it

edited 1×, last 28.02.12 03:10:24 am

Cs2d tibia tutorial ================ My new CS2D RPG Project Video

Anyways, Alistaire is still right. You have 1024 instaces of the same item with very very slight differences which is not efficient, plus, if you have like ten different items, you will have 10240 sub-types of these items.

Better to use prototyping instead. I don't really know if it's practical to implement in Tibia.

Better to use prototyping instead. I don't really know if it's practical to implement in Tibia.

Code:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

--Prototype for the item:

items =

{

[300] = {

name = "leather helmet",

desc = "Protect yourself from headshots!",

r = 128, g = 64, b = 0,

action = "equip",

slot = 1,

eimage = "gfx/weiwen/helmet.png",

fimage = "gfx/weiwen/helmet.png",

def = 0.05,

speed = -1,

func = equip,

}

}

prefix_num = 3

prefix_names = {"Hard","Light","Shiny"}

prefix_desc = {"+10% def", "+3 speed","Has a nice white color"}

prefix_stat = {

{10, "%", "def"},

{3, "+", "speed"},

{255, "=", "r,g,b"}

}

function generate_instance(prototype) --prototype should be 300 for this example

local t = table.copy(items[prototype])

local bonuses = {}

for i=1, math.random(0,prefix_num) do

local newstat = math.random(1,prefix_num)

while bonuses[newstat] do

newstat = newstat%prefix_num+1

end

bonuses[newstat] = true

t.name = prefix_names[newstat] .. t.name

t.desc = t.desc .." ".. prefix_desc[newstat]

for k, v in pairs(string.split(prefix_stat[newstat][3],",")) do --for each variable separated by comma

local operator = prefix_stat[newstat][2]

local ammount = prefix_stat[newstat][1]

if operator == "%" then

t[v] = t[v] + t[v]*ammount/100

elseif operator == "+" then

t[v] = t[v] + ammount

elseif operator == "=" then

t[v] = ammount

end

end

end

return t

end

--

--OUTPUT

--

local ins = generate_instance(300)

for k,v in pairs(ins) do

print(k..": "..v)

end

items =

{

[300] = {

name = "leather helmet",

desc = "Protect yourself from headshots!",

r = 128, g = 64, b = 0,

action = "equip",

slot = 1,

eimage = "gfx/weiwen/helmet.png",

fimage = "gfx/weiwen/helmet.png",

def = 0.05,

speed = -1,

func = equip,

}

}

prefix_num = 3

prefix_names = {"Hard","Light","Shiny"}

prefix_desc = {"+10% def", "+3 speed","Has a nice white color"}

prefix_stat = {

{10, "%", "def"},

{3, "+", "speed"},

{255, "=", "r,g,b"}

}

function generate_instance(prototype) --prototype should be 300 for this example

local t = table.copy(items[prototype])

local bonuses = {}

for i=1, math.random(0,prefix_num) do

local newstat = math.random(1,prefix_num)

while bonuses[newstat] do

newstat = newstat%prefix_num+1

end

bonuses[newstat] = true

t.name = prefix_names[newstat] .. t.name

t.desc = t.desc .." ".. prefix_desc[newstat]

for k, v in pairs(string.split(prefix_stat[newstat][3],",")) do --for each variable separated by comma

local operator = prefix_stat[newstat][2]

local ammount = prefix_stat[newstat][1]

if operator == "%" then

t[v] = t[v] + t[v]*ammount/100

elseif operator == "+" then

t[v] = t[v] + ammount

elseif operator == "=" then

t[v] = ammount

end

end

end

return t

end

--

--OUTPUT

--

local ins = generate_instance(300)

for k,v in pairs(ins) do

print(k..": "..v)

end

@ Flacko: You are right. What I was going to do is make over 1000 tables for each items and save it to a file . I'll try your method.

But I think the problem is that it would gives the player random item bonuses every time he re-equip the item, which is...not what i wanted.

Ok so should I come up with this? I will limit the amount of possible bonuses, like you can only have an item with 3 maximum bonuses rather than 10 bonuses. That way would greatly decrease the amount of instances.

If I come up with that, there would be 175 combinations for each item.

I'm planning to make 120 items, 120x175 = 21000 Item IDs

Comparing to 1023 combinations of item's bonus: 122760

21000

122760

Big difference

But I think the problem is that it would gives the player random item bonuses every time he re-equip the item, which is...not what i wanted.

Ok so should I come up with this? I will limit the amount of possible bonuses, like you can only have an item with 3 maximum bonuses rather than 10 bonuses. That way would greatly decrease the amount of instances.

If I come up with that, there would be 175 combinations for each item.

I'm planning to make 120 items, 120x175 = 21000 Item IDs

Comparing to 1023 combinations of item's bonus: 122760

21000

122760

Big difference

edited 2×, last 28.02.12 05:07:10 am

Cs2d tibia tutorial ================ My new CS2D RPG Project Video