4 Corrected the theory behind the code
source | link

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities with distinct integer powers is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entityany coalition of entities with less than half the power of all entities is Unstable.

(Thanks to Xerxes for pointing out the error in my original formulation).

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

**Edit:***The above code doesn't cover all the cases in the question as it assumed that one only needed to consider the stability of any subset formed by removing one element - look at Xerxes' answer below for a correct and faster implementation.*

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities with distinct integer powers is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities with distinct integer powers is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing any coalition of entities with less than half the power of all entities is Unstable.

(Thanks to Xerxes for pointing out the error in my original formulation).

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

**Edit:***The above code doesn't cover all the cases in the question as it assumed that one only needed to consider the stability of any subset formed by removing one element - look at Xerxes' answer below for a correct and faster implementation.*

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

3 added in condition to make question clearer
source | link

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities with distinct integer powers is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities with distinct integer powers is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

    Tweeted twitter.com/#!/StackMma/status/305035252424921088
2 Improved formatting
source | link

Optimizing Performance of Algorithm to Determine Stable Setsthe performance of Entitiesan algorithm

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[2*Max[#1]Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True,
  BitXor[Max[fstable /@ Subsets[#Subsets[#1, {Length[#]Length[#1] - 1}]], 1]]1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica'sMathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

Optimizing Performance of Algorithm to Determine Stable Sets of Entities

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[2*Max[#1] > Total[#1], 0, 2*Max[#1] == Total[#1], 1, True,
 BitXor[Max[fstable /@ Subsets[#, {Length[#] - 1}]], 1]] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

Optimizing the performance of an algorithm

First - a bit of an introduction. If you're only interested in the code, you can skip this section.

The following question is drawn from Dennis E. Shasha's Puzzling Adventures, and is listed under the question Strategic Bullying.

We have a set of entities, each of them with a power represented by a number. A coalition's power will be the sum of its members' powers. Coalition A will destroy Coalition B if A's power is greater than that of B, but A will back down if B can obtain enough new allies such that B's power is greater than or equal to A. When a coalition is beaten, it is destroyed and its wealth (proportional to its power) is distributed among the winners. The winners do not lose any of their power. Each of the entities plays selfishly, striving above all to avoid certain destruction but also to acquire wealth.

Based on the description of the question above, a set of entities is stable if there is a strong enough coalition to prevent any war and every member of that coalition has an interest in participating in the coalition.


Mathematically speaking, a set of entities is:

  • Unstable if the most powerful entity has more than half the total power of all entities, since it would destroy all other entities without being challenged;
  • Stable if the most powerful entity has exactly half of the total power of all entities, since it would not be able to destroy the other entities (they have an incentive to form a coalition to stop the most powerful entity;
  • and otherwise, Stable if and only if ALL subset of entities formed by removing one entity is Unstable.

What is the most efficient code we can write to check the stability of a given set of entities?

Now, I've written a function to check the stability of any given set of entities:

fstable = Which[
   2*Max[#1] > Total[#1], 0, 
   2*Max[#1] == Total[#1], 1,
   True, BitXor[Max[fstable /@ Subsets[#1, {Length[#1] - 1}]], 1]
   ] &;

Examples of implementation:

fstable[{3, 4, 5, 6}]
0

fstable[{3, 4, 5}]
1

However, this function does not run very fast, and in fact even checking the stability of a set of 10 entities takes some time:

Timing[fstable[Range[10]]]
{30.966199, 0}

Is there any way we can improve this, or will we require some additional mathematical insight to allow us to eliminate specific cases?


Note: The question the author actually asks is for us to find the largest set of entities with distinct integer powers and with the most powerful entity having a power of 21. To solve the problem by brute force, I would define the function using the idiom f[x_]:=f[x] to make use of Mathematica's ability to store function evaluations. However, the total number of function evaluations to be solved is quite large, so I'm not sure whether doing so will cause the kernel to run out of memory.

1
source | link