0

我正在制作一个 java 程序，它将通过生成所有可能的排列并检查是否有匹配来使用“蛮力”。示例：如果 G1 = “0-1 0-2 1-2 1-3 2-3”且 G2 = “1-3 2-0 0-3 1-2 1-0”，则排列 0123 → 2310 不匹配，但 0123 → 2013 匹配。

我需要创建一个图形类，将图形表示为二维布尔数组，并具有成员函数来检查 2 个顶点是否为边并打印图形。构造函数应该使用上面的字符串来表示一个边列表。

我需要知道如何以这种格式获取字符串并将其放入数组中。

总的来说，我想知道这两个图是否同构。

下面的代码是排列生成器。

// Generator of all permutations of: 0,1,2,...,n-1

public class PermutationGenerator
{
// private data

private int[] perm;
private boolean first;

// constructor

public PermutationGenerator (int n)
{
    perm = new int [n];
    first = true;
}


public int[] next ()
{
    int n = perm.length;

    // starting permutation: 0 1 2 3 ... n-1

    if (first)
    {
        first = false;
        for (int i = 0 ; i < n ; i++)
            perm [i] = i;
        return perm;
    }

    // construct the next permutation
    // find largest k so that perm[k] < perm[k+1]; if none, finish

    int i, j, k, l;

    for (k = n - 2 ; k >= 0 && perm [k] >= perm [k + 1] ; k--)
        ;
    if (k < 0)
        return null; // no more

    // find largest l so that perm[k] < perm[l]

    for (l = n - 1 ; l >= 0 && perm [k] >= perm [l] ; l--)
        ;

    // swap perm[k] and perm[l]

    swap (perm, k, l);

    // reverse perm[k+1]...perm[n-1]

    for (i = k + 1, j = n - 1 ; i < j ; i++, j--)
        swap (perm, i, j);

    return perm;
}


// swap a[i] and a[j]

private static void swap (int a[], int i, int j)
{
    int temp = a [i];
    a [i] = a [j];
    a [j] = temp;
}

}

4

2 回答 2

0

我认为有一种更简单的方法可以确定两个图（由字符串g1和表示g2）是否相同 - 怎么样：

new HashSet<String>(Arrays.asList(g1.split(" "))).equals(
                                new HashSet<String>(Arrays.asList(g2.split(" ")))

（如果我遗漏了什么，请告诉我）

如果您仍然想解析字符串并使用它来填充布尔邻接矩阵，您可以这样做：

  • 在空格上拆分邻接列表字符串以形成一个数组，称之为arr.
  • 循环arr，拆分每个元素"-"以形成一个新数组，调用它x（将为 的每个元素生成一个这样的数组arr，因为您正在循环它）。
  • 设置matrix[i][j]为true，其中i和j是x（分别）解析为整数的第一个和第二个元素。
于 2012-12-05T00:21:52.180 回答
0

使用 String.split() 在空间上拆分字符串，得到字符串数组 {0-1,0-2,1-2,1-3,2-3}。

遍历这些并在 - 上拆分以提取每个数字，然后您可以将其放入数组中。解析示例字符串的效率不是很高但很简单。

于 2012-12-05T00:23:21.260 回答