English [Math]Combination of words

26 replies
Goto Page
To the start Previous 1 2 Next To the start
27.02.12 04:42:41 pm
Up
KenVo
User
Offline Off
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)
27.02.12 04:49:49 pm
Up
MAX-russia
User
Offline Off
Its not possible really
27.02.12 04:52:54 pm
Up
Alistaire
User
Offline Off
You're making it too difficult.
IMG:http://i.imgur.com/5zhwOTP.png
27.02.12 05:54:29 pm
Up
Anders4000
User
Offline Off
I didn't even understand your question, be more specific.
27.02.12 06:14:09 pm
Up
BlazingStan
User
Offline Off
Erhm...
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
27.02.12 06:16:48 pm
Up
Nexmann
User
Offline Off
This isn't working.
27.02.12 06:18:21 pm
Up
BlazingStan
User
Offline Off
user 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,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
27.02.12 09:45:30 pm
Up
EngiN33R
Moderator
Offline Off
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
function math.factorial(n)
     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
27.02.12 09:47:26 pm
Up
BlazingStan
User
Offline Off
user 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
function math.factorial(n)
     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?
27.02.12 09:49:40 pm
Up
Alistaire
User
Offline Off
It's that he didn't state his question right..
IMG:http://i.imgur.com/5zhwOTP.png
27.02.12 09:50:26 pm
Up
DarkLight66
User
Offline Off
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.
Paradox
27.02.12 09:57:42 pm
Up
EngiN33R
Moderator
Offline Off
@user 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.
I code, therefore I exist. | Visit my blog for Lua tips and other interesting info
27.02.12 11:55:41 pm
Up
Lee
Moderator
Offline Off
So given the following definition of 'choosing' as

IMG:http://www.texify.com/img/%5CLARGE%5C%21%5Cleft%28%20n%20%5C%5C%20c%20%5Cright%29%20%3D%20%5Cfrac%7Bn%21%7D%7B%28n-c%29%21c%21%7D%20%3D%20%5Cprod_%7Bi%3D0%7D%5E%7Bc-1%7D%5Cfrac%7Bn-i%7D%7Bc-i%7D.gif


where order matters (so 'abc' is classified the same as 'bac'), then there are IMG:http://www.texify.com/img/%5CLARGE%5C%21%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%28%20n%20%5C%5C%20i%20%5Cright%29.gif
different combinations.

For the n=10 case, there are 1023 different combinations.
28.02.12 12:26:30 am
Up
Flacko
User
Offline Off
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
edited 1×, last 28.02.12 01:30:50 am
28.02.12 01:30:18 am
Up
Lee
Moderator
Offline Off
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)

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
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


using your test code

Code:
1
2
> see(solve({'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.
28.02.12 02:02:57 am
Up
KenVo
User
Offline Off
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:
@user 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.

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

@user 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.

@user Anders4000: Same as aboves
edited 12×, last 28.02.12 03:08:24 am
28.02.12 02:55:13 am
Up
Lee
Moderator
Offline Off
For the 4 case, we have the following possible combinations:

Code:
1
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


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.
28.02.12 03:00:22 am
Up
KenVo
User
Offline Off
user Lee has written:
For the 4 case, we have the following possible combinations:

Code:
1
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


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
28.02.12 04:10:37 am
Up
Flacko
User
Offline Off
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.

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
--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
28.02.12 04:38:15 am
Up
KenVo
User
Offline Off
@user 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
edited 2×, last 28.02.12 05:07:10 am
To the start Previous 1 2 Next To the start