{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2025-12-14T01:33:56.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2025-12-14T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":2244,"title":"Compute hamming distance between two binary vectors represented using lists of 1-byte numbers","description":"Let v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a \u003chttp://en.wikipedia.org/wiki/Hamming_distance Hamming distance\u003e between vectors formed by concatenation of binary representations of those numbers.\r\nFor example: \r\n\r\n  v = [1 0]\r\n  u = [1 255] \r\n\r\nBinary representations:\r\n  \r\n  v_bin = [00000001 00000000]\r\n  u_bin = [00000001 11111111]\r\n\r\nAnd the Hamming distance: \r\n\r\n  d = 0 + 8 = 8","description_html":"\u003cp\u003eLet v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a \u003ca href = \"http://en.wikipedia.org/wiki/Hamming_distance\"\u003eHamming distance\u003c/a\u003e between vectors formed by concatenation of binary representations of those numbers.\r\nFor example:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ev = [1 0]\r\nu = [1 255] \r\n\u003c/pre\u003e\u003cp\u003eBinary representations:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ev_bin = [00000001 00000000]\r\nu_bin = [00000001 11111111]\r\n\u003c/pre\u003e\u003cp\u003eAnd the Hamming distance:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ed = 0 + 8 = 8\r\n\u003c/pre\u003e","function_template":"function d = vHamming(u, v)\r\n  d = numel(u);\r\nend","test_suite":"%%\r\nu = 0;\r\nv = 0;\r\ny_correct = 0;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = 0;\r\nv = 127;\r\ny_correct = 7;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [1 0];\r\nv = [1 255];\r\ny_correct = 8;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [0 1];\r\nv = [255 0];\r\ny_correct = 9;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [0 128];\r\nv = [128 0];\r\ny_correct = 2;\r\nassert(isequal(vHamming(u, v),y_correct))","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":6084,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":41,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-03-12T12:32:47.000Z","updated_at":"2025-12-07T13:37:44.000Z","published_at":"2014-03-12T12:53:17.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eLet v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Hamming_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eHamming distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e between vectors formed by concatenation of binary representations of those numbers. For example:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[v = [1 0]\\nu = [1 255]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eBinary representations:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[v_bin = [00000001 00000000]\\nu_bin = [00000001 11111111]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAnd the Hamming distance:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[d = 0 + 8 = 8]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2303,"title":"Compute Hamming distances between each pair of rows from two input matrices","description":"For two input matrices _u_ ( _n_ x _uCols_ ) and _v_ ( _n_ x _vCols_ ) of numbers in range [0..255] (8-bit), such that each column represents an  _(8 x n)_-dimensional binary vector, calculate _uCols_ x _vCols_ matrix with each entry _(i,j)_ being a Hamming distance between _i_ -th and _j_ -th column from inputs _u_ and _v_ respectively.\r\n","description_html":"\u003cp\u003eFor two input matrices \u003ci\u003eu\u003c/i\u003e ( \u003ci\u003en\u003c/i\u003e x \u003ci\u003euCols\u003c/i\u003e ) and \u003ci\u003ev\u003c/i\u003e ( \u003ci\u003en\u003c/i\u003e x \u003ci\u003evCols\u003c/i\u003e ) of numbers in range [0..255] (8-bit), such that each column represents an  \u003ci\u003e(8 x n)\u003c/i\u003e-dimensional binary vector, calculate \u003ci\u003euCols\u003c/i\u003e x \u003ci\u003evCols\u003c/i\u003e matrix with each entry \u003ci\u003e(i,j)\u003c/i\u003e being a Hamming distance between \u003ci\u003ei\u003c/i\u003e -th and \u003ci\u003ej\u003c/i\u003e -th column from inputs \u003ci\u003eu\u003c/i\u003e and \u003ci\u003ev\u003c/i\u003e respectively.\u003c/p\u003e","function_template":"function y = hammings(u, v)\r\n  y = zeros(size(u,2),size(v,2));\r\nend","test_suite":"%% test 0\r\nq  = [0 \r\n      0];\r\ndb = [0 0\r\n      0 0];\r\nhamming_distances = [0 0];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n%% test 1\r\nq  = 128;\r\ndb = 4;\r\nhamming_distances = 2;\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n\r\n%% test 2\r\nq  = [  0   0 0 \r\n      128 128 0];\r\ndb = [128 255 0\r\n        0   0 0];\r\nhamming_distances = [2 9 1; 2 9 1; 1 8 0];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n\r\n%% test 3\r\nq  = [128  \r\n      128];\r\ndb = [255 0\r\n      255 0];\r\nhamming_distances = [14 2];\r\nassert(isequal(hammings(q, db), hamming_distances));\r\n\r\n\r\n%% test 4\r\nq  = [  0   0 0 \r\n      128 128 0];\r\ndb = [128 255\r\n        0   0];\r\nhamming_distances = [2 9; 2 9; 1 8];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":6084,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":15,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-05-01T17:29:58.000Z","updated_at":"2014-05-01T17:42:00.000Z","published_at":"2014-05-01T17:42:00.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor two input matrices\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eu\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003en\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003euCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ) and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ev\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003en\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003evCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ) of numbers in range [0..255] (8-bit), such that each column represents an \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e(8 x n)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e-dimensional binary vector, calculate\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003euCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003evCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e matrix with each entry\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e(i,j)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e being a Hamming distance between\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e -th and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ej\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e -th column from inputs\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eu\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ev\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e respectively.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2309,"title":"Calculate the Damerau-Levenshtein distance between two strings.","description":"\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices Problem 2303\u003e reminded me a few older ones dealing with metrics between strings, problems \u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings 93\u003e,\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings 846\u003e or\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings 848\u003e\r\n about Hamming and Levenshtein distances.\r\n\r\n\u003chttp://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance Damerau-Levenshtein distance\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\r\n\r\nAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\r\n\r\nExample. Such defined distance between words _gifts_ and _profit_ is 5:\r\n\r\n  gifts   =\u003e pgifts    (insertion of 'p')\r\n  pgifts  =\u003e prgifts   (insertion of 'r')\r\n  prgifts =\u003e proifts   (substitution of 'g' to 'o')\r\n  proifts =\u003e profits   (transposition of 'if' to 'fi')\r\n  profits =\u003e profit    (deletion of 's')\r\n  \r\n\r\n","description_html":"\u003cp\u003e\u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\"\u003eProblem 2303\u003c/a\u003e reminded me a few older ones dealing with metrics between strings, problems \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"\u003e93\u003c/a\u003e, \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\"\u003e846\u003c/a\u003e or \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\"\u003e848\u003c/a\u003e\r\n about Hamming and Levenshtein distances.\u003c/p\u003e\u003cp\u003e\u003ca href = \"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\"\u003eDamerau-Levenshtein distance\u003c/a\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/p\u003e\u003cp\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/p\u003e\u003cp\u003eExample. Such defined distance between words \u003ci\u003egifts\u003c/i\u003e and \u003ci\u003eprofit\u003c/i\u003e is 5:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003egifts   =\u0026gt; pgifts    (insertion of 'p')\r\npgifts  =\u0026gt; prgifts   (insertion of 'r')\r\nprgifts =\u0026gt; proifts   (substitution of 'g' to 'o')\r\nproifts =\u0026gt; profits   (transposition of 'if' to 'fi')\r\nprofits =\u0026gt; profit    (deletion of 's')\r\n\u003c/pre\u003e","function_template":"function distance = Damerau_Levenshtein(str1,str2)\r\n  distance = 0;\r\nend","test_suite":"%%\r\nassert(isequal(Damerau_Levenshtein('mom','dad'),3));\r\n% 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('dogs','dog'),1));\r\n% 1 deletion\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','true'),0));\r\n% identity\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','false'),4));\r\n% 1 insertion, 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('abc','ca'),2));\r\n% 1 deletion, 1 transposition\r\n%%\r\nassert(isequal(Damerau_Levenshtein('tee','tree'),1));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('email','mails'),2));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('profit','gifts'),5));\r\n%%\r\n% symmetry\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:10\r\n  str1=rnd();\r\n  str2=rnd();\r\n  a=Damerau_Levenshtein(str1,str2);\r\n  b=Damerau_Levenshtein(str2,str1);\r\n  assert(isequal(a,b))\r\nend\r\n%%\r\n% trinagle inequality\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:50\r\n  str1=rnd();\r\n  str2=rnd();\r\n  str3=rnd();\r\n  a=Damerau_Levenshtein(str2,str3);\r\n  b=Damerau_Levenshtein(str3,str1);\r\n  c=Damerau_Levenshtein(str1,str2);\r\n  assert(a+b\u003e=c)\r\nend","published":true,"deleted":false,"likes_count":1,"comments_count":8,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":45,"test_suite_updated_at":"2014-05-07T12:40:15.000Z","rescore_all_solutions":false,"group_id":32,"created_at":"2014-05-07T12:34:17.000Z","updated_at":"2026-03-26T02:24:43.000Z","published_at":"2014-05-07T12:40:15.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eProblem 2303\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e reminded me a few older ones dealing with metrics between strings, problems\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e93\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e846\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e848\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e about Hamming and Levenshtein distances.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eDamerau-Levenshtein distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample. Such defined distance between words\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003egifts\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eprofit\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is 5:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[gifts   =\u003e pgifts    (insertion of 'p')\\npgifts  =\u003e prgifts   (insertion of 'r')\\nprgifts =\u003e proifts   (substitution of 'g' to 'o')\\nproifts =\u003e profits   (transposition of 'if' to 'fi')\\nprofits =\u003e profit    (deletion of 's')]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":2244,"title":"Compute hamming distance between two binary vectors represented using lists of 1-byte numbers","description":"Let v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a \u003chttp://en.wikipedia.org/wiki/Hamming_distance Hamming distance\u003e between vectors formed by concatenation of binary representations of those numbers.\r\nFor example: \r\n\r\n  v = [1 0]\r\n  u = [1 255] \r\n\r\nBinary representations:\r\n  \r\n  v_bin = [00000001 00000000]\r\n  u_bin = [00000001 11111111]\r\n\r\nAnd the Hamming distance: \r\n\r\n  d = 0 + 8 = 8","description_html":"\u003cp\u003eLet v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a \u003ca href = \"http://en.wikipedia.org/wiki/Hamming_distance\"\u003eHamming distance\u003c/a\u003e between vectors formed by concatenation of binary representations of those numbers.\r\nFor example:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ev = [1 0]\r\nu = [1 255] \r\n\u003c/pre\u003e\u003cp\u003eBinary representations:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ev_bin = [00000001 00000000]\r\nu_bin = [00000001 11111111]\r\n\u003c/pre\u003e\u003cp\u003eAnd the Hamming distance:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ed = 0 + 8 = 8\r\n\u003c/pre\u003e","function_template":"function d = vHamming(u, v)\r\n  d = numel(u);\r\nend","test_suite":"%%\r\nu = 0;\r\nv = 0;\r\ny_correct = 0;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = 0;\r\nv = 127;\r\ny_correct = 7;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [1 0];\r\nv = [1 255];\r\ny_correct = 8;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [0 1];\r\nv = [255 0];\r\ny_correct = 9;\r\nassert(isequal(vHamming(u, v),y_correct))\r\n%%\r\nu = [0 128];\r\nv = [128 0];\r\ny_correct = 2;\r\nassert(isequal(vHamming(u, v),y_correct))","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":6084,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":41,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-03-12T12:32:47.000Z","updated_at":"2025-12-07T13:37:44.000Z","published_at":"2014-03-12T12:53:17.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eLet v and u be vectors of the same size with 8-bit integers (0-255). We want to compute the number of bits where those vectors differs i.e. a\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Hamming_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eHamming distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e between vectors formed by concatenation of binary representations of those numbers. For example:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[v = [1 0]\\nu = [1 255]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eBinary representations:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[v_bin = [00000001 00000000]\\nu_bin = [00000001 11111111]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAnd the Hamming distance:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[d = 0 + 8 = 8]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2303,"title":"Compute Hamming distances between each pair of rows from two input matrices","description":"For two input matrices _u_ ( _n_ x _uCols_ ) and _v_ ( _n_ x _vCols_ ) of numbers in range [0..255] (8-bit), such that each column represents an  _(8 x n)_-dimensional binary vector, calculate _uCols_ x _vCols_ matrix with each entry _(i,j)_ being a Hamming distance between _i_ -th and _j_ -th column from inputs _u_ and _v_ respectively.\r\n","description_html":"\u003cp\u003eFor two input matrices \u003ci\u003eu\u003c/i\u003e ( \u003ci\u003en\u003c/i\u003e x \u003ci\u003euCols\u003c/i\u003e ) and \u003ci\u003ev\u003c/i\u003e ( \u003ci\u003en\u003c/i\u003e x \u003ci\u003evCols\u003c/i\u003e ) of numbers in range [0..255] (8-bit), such that each column represents an  \u003ci\u003e(8 x n)\u003c/i\u003e-dimensional binary vector, calculate \u003ci\u003euCols\u003c/i\u003e x \u003ci\u003evCols\u003c/i\u003e matrix with each entry \u003ci\u003e(i,j)\u003c/i\u003e being a Hamming distance between \u003ci\u003ei\u003c/i\u003e -th and \u003ci\u003ej\u003c/i\u003e -th column from inputs \u003ci\u003eu\u003c/i\u003e and \u003ci\u003ev\u003c/i\u003e respectively.\u003c/p\u003e","function_template":"function y = hammings(u, v)\r\n  y = zeros(size(u,2),size(v,2));\r\nend","test_suite":"%% test 0\r\nq  = [0 \r\n      0];\r\ndb = [0 0\r\n      0 0];\r\nhamming_distances = [0 0];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n%% test 1\r\nq  = 128;\r\ndb = 4;\r\nhamming_distances = 2;\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n\r\n%% test 2\r\nq  = [  0   0 0 \r\n      128 128 0];\r\ndb = [128 255 0\r\n        0   0 0];\r\nhamming_distances = [2 9 1; 2 9 1; 1 8 0];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n\r\n\r\n%% test 3\r\nq  = [128  \r\n      128];\r\ndb = [255 0\r\n      255 0];\r\nhamming_distances = [14 2];\r\nassert(isequal(hammings(q, db), hamming_distances));\r\n\r\n\r\n%% test 4\r\nq  = [  0   0 0 \r\n      128 128 0];\r\ndb = [128 255\r\n        0   0];\r\nhamming_distances = [2 9; 2 9; 1 8];\r\nassert(isequal(hammings(q, db), hamming_distances ));\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":6084,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":15,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-05-01T17:29:58.000Z","updated_at":"2014-05-01T17:42:00.000Z","published_at":"2014-05-01T17:42:00.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor two input matrices\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eu\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003en\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003euCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ) and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ev\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003en\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003evCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ) of numbers in range [0..255] (8-bit), such that each column represents an \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e(8 x n)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e-dimensional binary vector, calculate\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003euCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e x\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003evCols\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e matrix with each entry\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e(i,j)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e being a Hamming distance between\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e -th and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ej\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e -th column from inputs\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eu\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ev\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e respectively.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2309,"title":"Calculate the Damerau-Levenshtein distance between two strings.","description":"\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices Problem 2303\u003e reminded me a few older ones dealing with metrics between strings, problems \u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings 93\u003e,\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings 846\u003e or\r\n\u003chttp://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings 848\u003e\r\n about Hamming and Levenshtein distances.\r\n\r\n\u003chttp://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance Damerau-Levenshtein distance\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\r\n\r\nAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\r\n\r\nExample. Such defined distance between words _gifts_ and _profit_ is 5:\r\n\r\n  gifts   =\u003e pgifts    (insertion of 'p')\r\n  pgifts  =\u003e prgifts   (insertion of 'r')\r\n  prgifts =\u003e proifts   (substitution of 'g' to 'o')\r\n  proifts =\u003e profits   (transposition of 'if' to 'fi')\r\n  profits =\u003e profit    (deletion of 's')\r\n  \r\n\r\n","description_html":"\u003cp\u003e\u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\"\u003eProblem 2303\u003c/a\u003e reminded me a few older ones dealing with metrics between strings, problems \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"\u003e93\u003c/a\u003e, \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\"\u003e846\u003c/a\u003e or \u003ca href = \"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\"\u003e848\u003c/a\u003e\r\n about Hamming and Levenshtein distances.\u003c/p\u003e\u003cp\u003e\u003ca href = \"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\"\u003eDamerau-Levenshtein distance\u003c/a\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/p\u003e\u003cp\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/p\u003e\u003cp\u003eExample. Such defined distance between words \u003ci\u003egifts\u003c/i\u003e and \u003ci\u003eprofit\u003c/i\u003e is 5:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003egifts   =\u0026gt; pgifts    (insertion of 'p')\r\npgifts  =\u0026gt; prgifts   (insertion of 'r')\r\nprgifts =\u0026gt; proifts   (substitution of 'g' to 'o')\r\nproifts =\u0026gt; profits   (transposition of 'if' to 'fi')\r\nprofits =\u0026gt; profit    (deletion of 's')\r\n\u003c/pre\u003e","function_template":"function distance = Damerau_Levenshtein(str1,str2)\r\n  distance = 0;\r\nend","test_suite":"%%\r\nassert(isequal(Damerau_Levenshtein('mom','dad'),3));\r\n% 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('dogs','dog'),1));\r\n% 1 deletion\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','true'),0));\r\n% identity\r\n%%\r\nassert(isequal(Damerau_Levenshtein('true','false'),4));\r\n% 1 insertion, 3 substitutions\r\n%%\r\nassert(isequal(Damerau_Levenshtein('abc','ca'),2));\r\n% 1 deletion, 1 transposition\r\n%%\r\nassert(isequal(Damerau_Levenshtein('tee','tree'),1));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('email','mails'),2));\r\n%%\r\nassert(isequal(Damerau_Levenshtein('profit','gifts'),5));\r\n%%\r\n% symmetry\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:10\r\n  str1=rnd();\r\n  str2=rnd();\r\n  a=Damerau_Levenshtein(str1,str2);\r\n  b=Damerau_Levenshtein(str2,str1);\r\n  assert(isequal(a,b))\r\nend\r\n%%\r\n% trinagle inequality\r\nrnd=@()char(randi([97 122],1,randi([4 10])));\r\nfor k=1:50\r\n  str1=rnd();\r\n  str2=rnd();\r\n  str3=rnd();\r\n  a=Damerau_Levenshtein(str2,str3);\r\n  b=Damerau_Levenshtein(str3,str1);\r\n  c=Damerau_Levenshtein(str1,str2);\r\n  assert(a+b\u003e=c)\r\nend","published":true,"deleted":false,"likes_count":1,"comments_count":8,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":45,"test_suite_updated_at":"2014-05-07T12:40:15.000Z","rescore_all_solutions":false,"group_id":32,"created_at":"2014-05-07T12:34:17.000Z","updated_at":"2026-03-26T02:24:43.000Z","published_at":"2014-05-07T12:40:15.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eProblem 2303\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e reminded me a few older ones dealing with metrics between strings, problems\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e93\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e846\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e848\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e about Hamming and Levenshtein distances.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eDamerau-Levenshtein distance\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAs it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample. Such defined distance between words\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003egifts\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eprofit\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is 5:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[gifts   =\u003e pgifts    (insertion of 'p')\\npgifts  =\u003e prgifts   (insertion of 'r')\\nprgifts =\u003e proifts   (substitution of 'g' to 'o')\\nproifts =\u003e profits   (transposition of 'if' to 'fi')\\nprofits =\u003e profit    (deletion of 's')]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"term":"tag:\"metric space\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"metric space\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"metric space\"","","\"","metric space","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f4f45e12120\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f4f45e12080\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f4f45e11720\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f4f45e12940\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f4f45e128a0\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f4f45e12300\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f4f45e121c0\u003e":"tag:\"metric space\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f4f45e121c0\u003e":"tag:\"metric space\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"search","password":"J3bGPZzQ7asjJcCk","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"metric space\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"metric space\"","","\"","metric space","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f4f45e12120\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f4f45e12080\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f4f45e11720\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f4f45e12940\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f4f45e128a0\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f4f45e12300\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f4f45e121c0\u003e":"tag:\"metric space\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f4f45e121c0\u003e":"tag:\"metric space\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":2244,"difficulty_rating":"easy-medium"},{"id":2303,"difficulty_rating":"easy-medium"},{"id":2309,"difficulty_rating":"medium-hard"}]}}