Re: Combinatorics question

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?


-- m

.

Relevant Pages

  • Re: Self function
    ... Python ... giving the programmer the ability to have a function refer to ... def parrot: ...     print inspect.getmembers ...
    (comp.lang.python)
  • Re: What c.l.pys opinions about Soft Exception?
    ... Actually, the latter is even less cluttered, misses a raise - if pure number ... Exception that aren't handled when no handler exists for it. ...     raise_soft ... def a_equal_b: ...
    (comp.lang.python)
  • Re: multiprocessing question/error
    ...     def calcula: ... def m1: ... from multiprocessing import Process, Pool ... def m2(self, arg): ...
    (comp.lang.python)
  • Re: How to launch a function at regular time intervals ?
    ...     func.start ... from datetime import datetime ... """Write timestamp in a file every 10 seconds in separate ... def stop: ...
    (comp.lang.python)
  • Re: question of style
    ...     if self.lower is None: ... values- Iterate through the values in sort order. ... def insert: ...
    (comp.lang.python)