Re: Combinatorics question

On 6 abr, 12:08, Mensanator <mensana...@xxxxxxx> wrote:
On Apr 6, 12:37 am, Mariano Suárez-Alvarez





<mariano.suarezalva...@xxxxxxxxx> wrote:
On 5 abr, 21:13, Mensanator <mensana...@xxxxxxx> wrote:

On Apr 5, 6:46�pm, Ketakop...@xxxxxxxxx wrote:

Thanks a lot for the help so far. It sure has been of much help. The
only thing is, that I'm having a bit of hard time understanding the
codes ;)

Whose? If it's MSA's code, that's understandable as
it's incorrect. Althought he does, in fact, generate
the correct count of C(10,4), all the numbers generated
end in '00', his minimum  number being 0000111100
instead of the correct 0000001111. And some of his
numbers have 12 bits. You'll find in gerneral that
generating wrong answers asymtotically faster isn't
better.

Ah. What I wrote and tested was:

  def subsets(n, i, min = 1):
      if i == 0:
          yield []
      elif n - min + 1 >= i:
          for m in xrange(min, n + 1):
              for s in subsets(n, i - 1, m + 1):
                  yield [m] + s

which enumerates the actual subsets and
messed up in trying to come up with

  def subsets(n, i, min = 1):
      if i == 0:
          yield 0
      elif n - min + 1 >= i:
          for m in xrange(min, n + 1):
              for s in subsets(n, i - 1, m + 1):
                  yield (1 << (m - 1)) + s

which instead enumerates numbers coding the
subsets. That's what one gets from not testing.

You are surely not contesting the claim
about efficiency, of course ;-)

No, of course not. Doesn't solve the OP's problem though.
Do you have an asymptotically faster way of doing the
Hamming Distance check?

I doubt there is a known algorithm to do what
the OP wants efficiently in general, and I
certainly do not have one. But simply replacing
your `while xrange(last)' loop by a loop using
my generator, the number of iterations in
the outer loop goes from exponential to
polynomial in the number of elements in the
set.

I do not think a brute force algorithm is
going to do much better. The Johnson graph
has a lot of structure, so it would not be
surprising that there is something different
one can do to obtain independent sets in it
efficiently. But to put the issue in
perspective, the size of a maximal independent
set in the Johnson graph is not known, so...

-- m


.

Relevant Pages

  • Re: How to copy multi object array contents into single object arrays?
    ... For people used to C-style languages, that loop will feel quite ... ECMAScript save the implicit conversion!), and in C99 you would use ... `i--' for maximum efficiency. ... The ascending order and the unnecessary pushcalls will decrease ...
    (comp.lang.javascript)
  • Re: How to copy multi object array contents into single object arrays?
    ... languages most recognizable for blocks delimited with curly braces. ... hoisting the loop bound.) ... As to the efficiency claims, ... I see differences in integer array look-ups, ...
    (comp.lang.javascript)
  • Re: Passive reradiating antenna
    ... loop the efficiency remains the same. ... > ferrite core material. ... For small permeabilities the capture area is much increased. ...
    (rec.radio.amateur.antenna)
  • Re: Efficiency question
    ... I just experimenting with a macro for the ... >don't always just code for efficiency". ... > ' Set this outside the loop as it saves an object ... > ' I've removed the True comparison but the compiler ...
    (microsoft.public.word.vba.general)
  • Efficiency of returning big objects
    ... I had a concern over the efficiency of returning big types, ... Iters: Natural; ... while Clock - Start < 1.0 loop ...
    (comp.lang.ada)