Message Boards Message Boards

0
|
7012 Views
|
8 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Find subset of strings with hamming weight n?

Posted 7 years ago

I am new to the language, I'm sure this question will sound very easy to most of you!

I would like to have a program which takes a set of strings and returns the subset of those strings with hamming weight n. I tried to do it like this:

Spaceweight[dim2_, n] := Module[{listi, weight, listinew},
  listinew = {};
  listi = SpaceF[dim2];
  For[cc = 1 <= Length[listi], cc++,
   If[DigitCount[listi, 2, 1] = n, listinew = Append[listinew, listi]];
   Return[listinew]];
  ]

but it doesn't even pretend to work. How would you go about doing this?

Thanks, Mary

POSTED BY: Mary Shepard
8 Replies

Mary,

What was the correct interpretation of your problem? Are your hamming strings lists of binary digits or character strings? Curious as to which approach you are using...

POSTED BY: Neil Singer
Posted 7 years ago

The correct interpretation was

SelectHamming

I am very grateful for your help, I didn't think of simply counting the 1's, I was stuck trying to make it work with the HammingDistance since that is what I found when looking for "hamming weight". The bulk of the workaround (generating a list of 0's of length 2^(2^n) and calculating the hamming distance to that) meant that I ran out of memory already with functions on 6 variables (strings of length 32) Beginners mistake!

I am working on bent functions, (maximally nonlinear boolean functions) and it gets unwieldy pretty fast. I narrowed down the list where interesting functions lived with a little program called spaceF, and I needed to feed subsets of that space with hamming weight n into another program.

Mary

POSTED BY: Mary Shepard

Mary,

I think the confusion is that Mathematica "strings" involve text strings as Sander demonstrated. I believe that your "strings" are lists of binary digits (and not Mathematica strings). If this is correct, This should work for you:

In[2]:= list = Range[15]
Out[2]= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

IntegerDigits converts my list of numbers to 4 digit binary "Strings" in Mathematica -- these are lists of digits

In[3]:= mylist = Map[IntegerDigits[#,2,4]&,list]
Out[3]= {{0,0,0,1},{0,0,1,0},{0,0,1,1},{0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},{1,0,0,0},{1,0,0,1},{1,0,1,0},{1,0,1,1},{1,1,0,0},{1,1,0,1},{1,1,1,0},{1,1,1,1}}

Make a function that picks out the lists with a certain number of 1's

In[5]:= SelectHamming[str_List,n_Integer]:=Select[str,Count[#,1]==n&]
In[6]:= SelectHamming[mylist,2]
Out[6]= {{0,0,1,1},{0,1,0,1},{0,1,1,0},{1,0,0,1},{1,0,1,0},{1,1,0,0}}

I hope this helps

POSTED BY: Neil Singer

Or, may be this is the solution:

listofstrings = {"hello", "test", "apple", "banana", "world", "soap", "man", "an", "Hamming", "dodecahedron", "Wolfram Community",  "Wolfram Language", "Paintings"};
SelectHammingWeight[x_List, z_String, n_Integer] := Select[StringJoin /@ StringSplit[x, z], StringLength[#] == n &]
Manipulate[SelectHammingWeight[listofstrings, "a", n], {n, 1, 16, 1}]
Posted 7 years ago

THANK YOU SO MUCH. This works perfectly!

Mary

POSTED BY: Mary Shepard

what is SpaceF? Could you give an example of a minimal input, and the output it should have? If I understood your problem correctly, I would do something like:

listofstrings={"hello","test","apple","banana","world","soap"}
SelectHammingWeight[lst_List,char_String,n_Integer]:=Select[lst,StringCount[#,char]==n&]
SelectHammingWeight[listofstrings,"a",1]

that would output strings which have 1 "a" in it.

POSTED BY: Sander Huisman
Posted 7 years ago

Thanks, but I still can't tweak it to work with my input.

SpaceF takes an integer and returns a list of binary strings like say [{0,0,1,1}, {0,1,1,1},{1,0,0,0}]. What I really want is a program which works with SpaceF so that I can generate a sublist of all entries with hamming weight n.

Mary

POSTED BY: Mary Shepard

It would be good to add an input and an expected output, your description is not entirely clear now...

POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract