0

我使用二进制数,并尝试在数组中找到两个仅在一个差异之间的字符串。例如

string[]binary = {"{0000}","{0001}","{0111}"};

只有第四个字符对于第一个和第二个元素是不同的,我应该证明这一点,那么我怎样才能找到它们呢?C#中有什么有效的方法吗?谢谢..

4

3 回答 3

1

这可能会有所帮助:

public static int StringDistance(string first, string second)
{
    int result = 0;

    for (int i = 0; i < first.Length; i++)
    {
        if (!first[i].Equals(second[i]))
        {
            result++;
        }
    }

    return result;
}

你可以这样使用它:

string[] binary = { "{0000}", "{0001}", "{0111}" };
var result = binary.Where(input => binary.Any(i => StringDistance(i, input) == 1)).ToArray();
//output: {"0000", "0001"}
于 2013-03-29T17:49:45.523 回答
0

怎么样,它会找到所有具有一个不同位的二进制数:

class Program {
    static void Main( string[ ] args ) {
        string[] binary = { "{0000}", "{0001}", "{0111}" };
        var differentNumbers = DifferentNumbers( binary );

        foreach ( Tuple<string, string, int> tuple in differentNumbers )
            Console.WriteLine( string.Format( "{0} ; {1} - index {2}", tuple.Item1, tuple.Item2, tuple.Item3 ) );
    }

    public static List<Tuple<string, string, int>> DifferentNumbers( string[ ] array ) {
        var differentNumbers = new List<Tuple<string, string, int>>( );

        for ( int i = 0; i < array.Length; i++ ) {
            for ( int j = i + 1; j < array.Length; j++ ) {

                int count = 0, index = 0;
                for ( int c = 1; c < array[ i ].Length - 1; c++ ) {
                    if ( array[ i ][ c ] != array[ j ][ c ] ) {
                        index = c;
                        if ( count++ > 1 )
                            break;
                    }
                }

                if ( count == 1 )
                    differentNumbers.Add( new Tuple<string, string, int>( array[ i ], array[ j ], index ) );
            }
        }

        return differentNumbers;
    }
}

结果:

{0000} ; {0001} - 索引 4

于 2013-03-29T17:46:45.697 回答
0

遍历每个字符串一次以转换为 UInt64,然后可以非常有效地多次使用以相互测试:

    static private void TestCheckFor1BitDiff()
    {
        string[] values = new string[]
        {
            "0000",
            "0001",
            "0111",
            "1000",
            "1111"
        };

        UInt64[] intValues = values.Select(v => ConvertBinaryToUInt64(v)).ToArray();

        bool comp01 = CheckFor1BitDiff(intValues[0], intValues[1]); // true
        bool comp02 = CheckFor1BitDiff(intValues[0], intValues[2]); // false
        bool comp12 = CheckFor1BitDiff(intValues[1], intValues[2]); // false
        bool comp03 = CheckFor1BitDiff(intValues[0], intValues[3]); // true
        bool comp24 = CheckFor1BitDiff(intValues[2], intValues[4]); // true
    }

    private static UInt64 ConvertBinaryToUInt64(string value)
    {
        if (64 < value.Length)
        {
            throw new ArgumentException("exceeds 64 bits", "value");
        }

        UInt64 power = 1;
        UInt64 retVal = 0;

        foreach (char bit in value.ToArray().Reverse())
        {
            switch (bit)
            {
                case '1':
                    retVal += power;
                    break;
                case '0':
                    break;
                default:
                    throw new ArgumentException("contains characters other than 0 and 1", "value");
            }

            power *= 2;
        }

        return retVal;
    }

    static private bool CheckFor1BitDiff(string a, string b )
    {
        UInt64 a1 = ConvertBinaryToUInt64(a);
        UInt64 b1 = ConvertBinaryToUInt64(b);

        return CheckFor1BitDiff(a1, b1 );
    }

    static private bool CheckFor1BitDiff(UInt64 a, UInt64 b )
    {
        return IsPowerOfTwo( a ^ b );
    }

    static private bool IsPowerOfTwo(UInt64 value)
    {
        return (value & (value - 1)) == 0;
    }
于 2013-03-29T18:24:38.320 回答