[algogeeks] Re: Permutation with a twist ??
On Feb 2, 5:02 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> Hey,
>
> I am looking for an algorithm to do as follows:
>
> my @array = qw (A B C); # This array may have several parameters,
> for
> ex. A B C D
>
> I will like to generate following (not sure if this will be called
> permutation):
>
>
> C
> B
> A
> B C
> A C
> A B
> A B C
>
> Available permutation algorithms generate a different output, for
> example:
> b c a
> c b a
> c a b
> a c b
> b a c
> a b c
>
> Any suggestions! Thanks in advance.
This is called the power set. You can easily generate the power set
by identifying each of the original elements with a digit in a binary
number and then counting. The 1's in the successive counts tell you
whether to include the element in the current output or not.
Identify binary digits cba with C B A:
000 = {}
001 = A
010 = B
011 = BA
100 = C
101 = CA
110 = CB
111 = CBA
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: puzzle - Weighing marbles
Split the marbles into sets of 4 each
Compare the first and second sets
If both the sets are equal (the problem is in third set)
{
choose 2 of the marbles in the third set
compare with 2 marbles from the first set(which we know are good)
if comparision is equal
{
compare one of the remaining 2 marbles in the third set with a good marble
if comparison is equal
culprit is the uncompared marble in the third set
else
culprit is the last chosen marble in the third set
}
else
{
compare one of the chosen 2 marbles in the third set with a good marble
if comparison is equal
culprit is the uncompared marble in the chosen 2 of the third set
else
culprit is the last chosen marble in the third set
}
}
else
{
choose one of the marbles from the first pan and shift to second pan
remove the other 3 marbles from the second pan and put 3 from the third pan
If the comparison value changes (now < , previous > or vice versa)
{
one of the transferred 2 marbles is the culprit
found by comparing one of the marble with a standard one (from third set)
}
else
{
If comparison value is equal
{
one of the three marbles from second pan was the culprit (we
know heavier or lighter now ...from the first comparison)
can be determined by comparing two of the marbles
if equal
third guy is the culprit
else
the (heavier or ligher guy) as determined by the first comparison
}
else (comparison values are same)
{
one of the three unshifted marbles from the first pan is the culprit
can be found in a strategy similar to the previous cases
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: puzzle - Weighing marbles
We don't know if the marble is heavier or lighter ... which makes it interesting :) Here's a very clever solution: http://mathforum.org/kb/message.jspa?messageID=1085028&tstart=0 On 2/2/07, aditi saha <[EMAIL PROTECTED]> wrote: > > Do you know if the faulty marble is lighter or heavier? > > On 2/2/07, Atamurad Hezretkuliyev <[EMAIL PROTECTED] > wrote: > > > > > > Hi, > > > > Can somebody help me with this puzzle? I tried to solve it but couldn't. > > > > > > > > Puzzle 1 > > Weighing marbles > > Given are 12 marbles. One of these marbles is slightly heavier or > > lighter than the others. You have a two plate scale. You are allowed > > to weigh three times. > > Can you find the marble that differs in weight? > > > > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: puzzle - Weighing marbles
Do you know if the faulty marble is lighter or heavier? On 2/2/07, Atamurad Hezretkuliyev <[EMAIL PROTECTED]> wrote: > > > Hi, > > Can somebody help me with this puzzle? I tried to solve it but couldn't. > > > Puzzle 1 > Weighing marbles > Given are 12 marbles. One of these marbles is slightly heavier or > lighter than the others. You have a two plate scale. You are allowed > to weigh three times. > Can you find the marble that differs in weight? > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
I'm sorry. My algo is terribly wrong!
On 2/3/07, Rajiv Mathews <[EMAIL PROTECTED]> wrote:
>
> Combination(Array Elements, Array Answer)
> {
> if(Elements.size() == 0) print Answer, return;
> for(i in Elements)
>//Select the particular element -- equiv to 1 say
>Combinations(Elements+1, Answer.push_back(Elements[0])
>//Don't select the element -- equiv to 0 say
>Combinations(Elements+1, Answer)
> }
>
It should be,
Combinations(Array Elements, Array Answer, int size)
{
if(size == 0) print(Answer);
//Select element
Answer.push_back(Elements[0]);
Combinations(Elements+1, Answer, size-1);
Answer.pop_back();
//Don't select element
Combinations(Elements+1, Answer, size-1);
}
Sorry for the last post. I shouldn't be typing while sleeping :-)
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
yes..i agree with rajiv..you seem to be generating combinations rather than permutations..the algo that i have given generates permutations --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] puzzle - Weighing marbles
Hi, Can somebody help me with this puzzle? I tried to solve it but couldn't. Puzzle 1 Weighing marbles Given are 12 marbles. One of these marbles is slightly heavier or lighter than the others. You have a two plate scale. You are allowed to weigh three times. Can you find the marble that differs in weight? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
On 2/3/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> I will like to generate following (not sure if this will be called
> permutation):
>
>
> C
> B
> A
> B C
> A C
> A B
> A B C
>
I think you're looking to generate all possible combinations of n elements.
Essentially below I'm trying to simulate binary,
Combination(Array Elements, Array Answer)
{
if(Elements.size() == 0) print Answer, return;
for(i in Elements)
//Select the particular element -- equiv to 1 say
Combinations(Elements+1, Answer.push_back(Elements[0])
//Don't select the element -- equiv to 0 say
Combinations(Elements+1, Answer)
}
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
permutation (List resultSoFar, List remainingElements)
{
if(length(remainingElements)=0)
return;
for i = 1 to length(remainingElements)
{
print resultSoFar+remainingElements[i];
permutation (resultSoFar+remainingElements[i],
remainingElements-remainingElements[i]);
}
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Permutation with a twist ??
Hey, I am looking for an algorithm to do as follows: my @array = qw (A B C); # This array may have several parameters, for ex. A B C D I will like to generate following (not sure if this will be called permutation): C B A B C A C A B A B C Available permutation algorithms generate a different output, for example: b c a c b a c a b a c b b a c a b c Any suggestions! Thanks in advance. Manish --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
