In this paper, we consider the problem of computing a minimum k-partition of a finite set V with a set function f : 2(V) -> R, where the cost of a k-partition {V-1, V-2,..., V-k} is defined by Sigma(1 <= i <= k)f (V-i). This problem contains the problem of partitioning a vertex set of an edge-weighted hypergraph into k components by removing the least cost of hyperedges. We show that, for a symmetric and submodular set function f, 2(1-1/k)-approximate solutions for all k epsilon [1,vertical bar V vertical bar] can be obtained in O(vertical bar V vertical bar(3))-oracle time. This improves the previous best time bound by a factor of k = O(vertical bar V vertical bar).